科学方法

　　科学家用来理解自然世界的方法(科学方法)对于研究程序的运行时间同样有效。科学方法包含以下几个方面：

• 采用准确的方法来观察自然界的一些现象
• 假设出一个与观察到的现象一致的模型
• 使用假设来预测事件
• 通过进一步观察来验证预测
• 重复验证，直到假设和观察结果一致

　　科学方法的一个关键原则是我们设计的实验必须要具有可重现性，以便其他人能够说服自己该假设的有效性。假设也必须是可证伪的，这样我们能确定地知道给定的假设什么时候是错误的（因此需要修正）。我们永远无法确定任何假设是绝对正确的；我们只能验证它是否与我们的观察结果一致。

　　我们面临的第一个挑战就是如何对程序的运行时间进行定量测量。 很简单，运行这个程序就可以了。你每次运行一个程序，你就是在进行一项实验并回答一个核心问题：我的程序要运行多长时间？

　　我们对大多数程序的第一个定量观察是，计算任务的难度可以用问题的规模来衡量。正常情况下，问题的规模，或指的是输入的规模，或指的是输入的值。直觉告诉我们，程序的运行时间应该会随着问题的规模增长而增长，但问题是，每次我们开发和运行一个程序时，运行时间会增加多少呢？

　　许多程序的另一个定量观察是，运行时间对输入值本身相对不敏感，它主要取决于问题的规模。如果这种关系不成立，我们需要采取措施更好地理解，也许更好地控制运行时间对输入的敏感性。但它经常成立，所以我们现在把注意力集中在更好地量化问题规模和运行时间之间的关系。

　　作者举了一个ThreeSum的例子，来展示运行时间和输入规模的关系。Three Sum 就是从Ｎ个整数中找出所有和为０的三个整数元组的个数

public class ThreeSum {
    public static int count(int[] a) {
        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;
    }

}

　　同时给了一个Stopwatch类来测量程序的执行时间

class Stopwatch {
    private final long start;

    public Stopwatch() {
        start = System.currentTimeMillis();
    }

    public double elapsedTime() {
        long now = System.currentTimeMillis();
        return (now - start) / 1000.0;
    }
}

　　执行DoublingTest程序来看一个时间和问题规模之间的关系

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;

public class DoublingTest {
    public static double timeTrial(int N) {
        int MAX = 1000000;
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = StdRandom.uniform(-MAX, MAX);
        Stopwatch timer = new Stopwatch();
        int cnt = ThreeSum.count(a);
        return timer.elapsedTime();
    }

    public static void main(String[] args) { // Print table of running times.
        for (int N = 250; true; N += N) { // Print time for problem size N.
            double time = timeTrial(N);
            StdOut.printf("%7d %5.1f\n", N, time);
        }
    }
}

　　得出一个结论，如果程序的输入规模是Ｎ，那么程序的运行时间T(N) = aN³ , 或者lg(T(N )) = 3 lg N + lg a，a为常数。

　　数学方法

　　除了科学方法，数学方法也可以推导出程序的运行时间和输入规模Ｎ的关系。简单来说，程序的运行时间是由两个因素决定的。一个是每条语句的执行时间，这由计算机本身决定，你的计算机CPU性能高，执行就快，时间就短。一个是每条语句的执行频率，这通常是程序和输入规模决定的。所以算法分析，一个主要的挑战就是决定语句的执行频率。有些语句分析起来比较容易，比如 int cnt = 0;, 它就执行了一次。有些就比较复杂了，比如 if(arr[i] + a[j] + a[k] ==0) ，它执行了多少次呢？它执了N (N - 1)(N - 2)/6 次。为什么呢？整个循环加上if语句，表达出来的意思是，从n个数里面选取3个，组合为C(n,3)=n(n-1)(n-2)/(3*2*1)。

　　这类频率分析可能导致复杂且冗长的数学表达式，比如N (N - 1)(N - 2)/6= N3 /6 - N2 /2  + N/3，这是一种典型的表达式，就是首项(第一项或高阶项)后面的其它项，相对较小。比如当Ｎ=1000的时候， -N² /2  + N/3的值是499,667, 和 N³ /6 =166,666,667 一比较，它就不重要了。我们经常使用～符号来忽略不重要的项，简化我们所处理的数学公式，这个符号使我们以近似的方式工作，它舍弃了低阶项。

　　当Ｎ增长时，函数除以f(N) 趋近于１，我们用～f(N) 来表示这些函数。g(N ) ~ f (N ) 就表示，当Ｎ增长时，g(N )/f (N )趋近于１。比如，我们使用近似值～N³ /6来描述ThreeSum函数中if语句的执行次数，因为当Ｎ增长时，N³ /6 - N² /2  + N/3除以N³ /6)趋近于１。通常，我们都使用g(N ) ~ af (N )这种近似方式，其中f (N ) = N^b (log N )^c ， a, b, and c是常数。f(N) 也称为g(N)的增长阶。当在增长阶中使用对数时，我们一般不指定对数底。g(N ) ~ af (N )这种表达式，覆盖了我们在对程序过行时间研究中经常遇到的几种函数，比如１，n，n^３。怎么说呢？

　　当a=１，b=０，c=０时，　g(N ) ~ aN^b (log N )^c-> g(N ) ~ 1 N⁰(logN)⁰  -> g(N) ~ 1  常数增长级。

　　当a=１，b=０，c=１时，　g(N ) ~ aN^b (log N )^c-> g(N ) ~ 1 N⁰(logN)¹  -> g(N) ~ logN  对数增长级。

　　当a=１，b=１，c=１时，　g(N ) ~ aN^b (log N )^c-> g(N ) ~ 1 N¹(logN)¹ -> g(N) ~ NlogN  线性对数增长级。

　　知道每条语句的执行频率，就能计算出程序的运行时间。根据执行频率将Java程序语句分块，然后计算出执行频率的近似值，如下图所示

　　决定每条语句的执行时间，真正的执行时间涉及到计算机，编译器，比较复杂，通常用常数t0, t1, t2 ..... 来表示这个代码块的执行时间，

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