博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
homework-01
阅读量:5874 次
发布时间:2019-06-19

本文共 2710 字,大约阅读时间需要 9 分钟。

我选择的书是代码大全

一. 程序的架构和思路:

朴素算法就是一个三重循环,但是当n极大的时候,时间会爆表。

 

#include
#include
using namespace std;int max(int x,int y){ if (x > y) return x; else return y;}int main(){ int n,a[10010]; int i,j,k,ans,temp; while (scanf("%d",&n) != EOF) { for (i = 0;i < n;i++) scanf("%d",&a[i]); ans = a[0];//确定下界 for (i = 0;i < n;i++) for (j = i;j < n;j++) { temp = 0; for (k = i;k <= j;k++) temp = temp + a[k];//累加 ans = max(ans,temp); } printf("%d\n\n",ans); } return 0;}

 

此算法容易理解,时间复杂度为O(n^3)。

继续想其他优化,其实这个可以看做两个求和问题,求i到j的和可以看做1到j的和减去1到i的和,于是可用树状数组优化。

等等...不会这么复杂吧...

利用树状数组优化可将时间复杂度降至O(n^2*(logn)^2),还是有点大,而且代码量太长,效率不够高。

回看第一种方法,其做了很多冗余的操作,例如,先计算i到j,之后继续计算i到j+1,于是可从上一步的值过渡到下一步,因此也就可以消掉一重循环。

#include
#include
using namespace std;int max(int x,int y){ if (x > y) return x; else return y;}int main(){ int n,a[10010]; int i,j,ans,sum; while (scanf("%d",&n) != EOF) { for (i = 0;i < n;i++) scanf("%d",&a[i]); ans = a[0];//确定下界 for (i = 0;i < n;i++) { sum = 0; for (j = i;j < n;j++) { sum = sum + a[j];//从上一步继续加 ans = max(ans,sum); } } printf("%d\n\n",ans); } return 0;}

由此可见,此算法时间复杂度为O(n^2),但是n极大的时候依旧会爆表,所以,我觉得能继续优化。

如果我们不需要知道最大子序列位置的话,i循环似乎就没有用了。

若i到j为最大子序列,那么a[i]不可能为负,因为若a[i]为负,a[i+1]为正,则i+1到j为最大。

所以我们可以这么认为,若枚举到i到j阶段时,此阶段和为0,则可舍去,最大子序列必不包含此阶段。

不过需要注意的是,若a数组全为负,则程序输出为0,于是需要加个一重循环特判下界。

#include
#include
using namespace std;int max(int x,int y){ if (x > y) return x; else return y;}int main(){ int n,a[10010]; int i,ans,sum; while (scanf("%d",&n) != EOF) { for (i = 0;i < n;i++) scanf("%d",&a[i]); ans = a[0]; for (i = 1;i < n;i++) ans = max(ans,a[i]);//特判下界 sum = 0;ans = 0; for (i = 0;i < n;i++) { sum = sum + a[i]; if (sum > ans) ans = sum; else if (sum < 0) sum = 0;//若小于0则舍去 } printf("%d\n\n",ans); } return 0;}

由此可见,此算法时间复杂度为O(n),应该能够应对大部分数据了。

二. 写这个程序的心得:

心得算不上,说说优化的想法吧。

首先需要写出程序的朴素算法,不管时间复杂度有多高。

然后需要列出自己所做的无用功,看代码,是否可以通过上一步得出这一步,这是动态规划的思想:用空间换时间。

也可以尝试利用分治的思想,将n优化为logn(很遗憾这题我没想明白怎么分治...)。

最重要的是要细心,看自己是否理解错了题意,多做了工作,是否可以省略掉。

三. 程序时间消耗与开发效率分析:

这点做得不够好,因为我不会用程序的计时功能...

不过可以根据程序本身算出时间复杂度,自然,3个程序的时间复杂度是递减序列,但是开发时间却是递增序列。

还是秉承着越好的算法需要越长的时间去构思0.0

四. 程序运行截图:

其实说实话这个没有太大意义...3个程序运用的数据相同,自然截图也是相同的...

五. 感想与不足:

此课程感觉是算法设计的进阶,由于我算法学的还算不错,因此对于目前的作业来说还是能玩得转的。

但是,不同于算法的是,我需要提交程序运行时间...

争取在下次作业提交前学会怎么计时吧...

 

转载于:https://www.cnblogs.com/yimingzou/p/3329563.html

你可能感兴趣的文章
How can I set ccshared=-fPIC while executing ./configure?
查看>>
2.移植uboot-添加2440单板,并实现NOR、NAND启动
查看>>
hadoop-2.6.5安装
查看>>
vmware虚拟机里的LINUX不能上网的原因一:虚拟网卡设置
查看>>
监控摄像机的区别和分类
查看>>
Java学习——对象和类
查看>>
ElasticSearch 组合过滤器
查看>>
HttpClient连接池的连接保持、超时和失效机制
查看>>
1-4 多文档界面处理(2)
查看>>
《Essential Linux Device Drivers》中文版第1章
查看>>
让远程传输大文件变得更快
查看>>
complex的小困惑
查看>>
十进制、十六进制、二进制的转换
查看>>
双网卡centos7 iptables防火墙与/etc/rc.d/rc.local开机运行
查看>>
tomcat PermGen space 不足的解决方法
查看>>
STM32系统滴答_及不可不知的延时技巧 - (上)
查看>>
Linux下企业级分区方案
查看>>
CentOS下LAMP一键yum安装脚本
查看>>
拖来拖去今天终于重装系统了
查看>>
NestJS 脑图
查看>>