首页 > 代码库 > 普林斯顿公开课 算法1-2:观察
普林斯顿公开课 算法1-2:观察
这章通过一个简单的例子,详细说明算法分析的步骤。
算法
问题
给定N个不同的整数,从中任意取出三个整数。请问有几种情况,使得取出的3个整数之和为0?
解法
可以使用暴力算法,代码如下:
1 2 3 4 5 6 7 8 9 | for ( int i= 0 ;i<N;i++){ for ( int j= 0 ;j<N;j++){ for ( int k= 0 ;k<N;k++){ if (a[i]+b[i]+a[k]== 0 ){ count++; } } } } |
算法分析
观察
输入的整数数量与算法运行时间的曲线图
将x轴和y轴都进行log变换,得到下图:
由于图中是直线,所以输入数据量和时间的关系符合a*N^b。
假设
运行时间大约是1.006×10^-10×N^2.999秒。
预测
N=8000时,运行时间是51.0秒
N=16000时,运行时间是408.1秒
观察
N=16000时,实际运行时间是410.8秒,符合预测。所以建立的模型是比较正确的。
运行时间的影响因素
算法的运行时间不但跟输入的数据量有关,跟算法本身也有关。除了这些内部因素,还有很多外部因素也会影响算法的运行时间,比如CPU的性能、内存性能、系统中其他进程的情况。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。