首页 > 代码库 > 普林斯顿公开课 算法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的性能、内存性能、系统中其他进程的情况。