算法(3) 算法分析

人们在使用计算机解决困难问题或是处理大量数据时不可避免的将会产生这样的疑问：
“我的程序会运行多长时间？”
“为什么我的程序耗尽了所有内存？”

尽管有这些困难，你在本节中将会看到，为这些基础问题给出实质性的答案有时其实非常简单。这个过程的基础是科学方法，它是科学家们为获取自然界知识所使用的一系列为大家所认同的方法。我们将会使用数学分析为算法成本建立简洁的模型并使用实验数据验证这些模型。

1、科学方法　　　　　　

科学家用来理解自然世界的方法对于研究计算机程序的运行时间同样有效：

.细致的观察真实世界的特点，通常还要有精确的测量；
.根据观察结果提出假设模型；
.根据模型预测未来的事件；
.继续观察并核实预测的准确性；
.如此反复直到确认预测和观察一致。

举例：

ThreeSum程序会统计一个文件中所有和为0的三整数元组的数量(假设整数不会溢出)。这种计算可能看起来不太自然，但其实它和很多基础计算性任务都有着深刻的联系。

package algorithm;

import stdLib.In;
import stdLib.StdOut;

/**
 * 〈〉<br>
 */
public class ThreeSum {
    public static int count(int[] a){
        //统计和为0的元组的数量
        int N = a.length;
        int cnt = 0;
        for(int i=0; i<N; i++){
            for(int j=i+1; j<N; j++){
                for(int k=j+1; k<N; k++){
                    if(a[i] + a[j] + a[k] == 0){
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }

    public static void main(String[] args) {
        int[] a = In.readInts(args[0]);
        StdOut.println(count(a));
    }
}

事实上，对于算法的分析，我们有许多数学模型强烈支持这种函数和其他类似的假设，我们现在就来学习他们。

 

2、数学模型　　　　　　

常见的增长数量级函数

增长的数量级
描述                        函数
常数级别                    1
对数级别                    logN
线性级别                    N
线性对数级别                 NlogN
平方级别                    N²
立方级别                    N³
指数级别                    2的N次方

我们观察到的一个关键现象是执行最频繁的指令决定了程序执行的总时间——我们将这些指令成为程序的内循环。对于ThreeSum来说，它的内循环是将k+1、判断它是否小于N以及判断给定的三个整数之和是否为0的语句(也许还包括记数的语句，不过这取决于输入)。这种情况是很典型的:许多程序的运行时间都只取决于其中的一小部分指令。