算法效率的度量方法

上一章提到的设计算法要尽量提高效率，这里效率高一般指的是算法的执行时间短

事后统计

这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低

但是这个方法有比较大的缺陷

必须要依据算法事先编写好测试程序，通常需要花费大量的时间和精力，但是测试出来的结果并不理想时，就花费了大量的无用功
不同的测试环境差别比较大

事先估算

在算法编写前，依据统计方法对算法进行估算

经过总结，算法在计算机运行时所消耗的时间取决于以下因素：

算法才用的策略、方案
编译产生的代码质量（编译器的优劣有比较大的影响）
问题的输入规模
机器执行指令的速度（硬件方面）

由此可见，在不考虑计算机硬件（指令执行速度）、软件（语言、编译器）的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模（输入量）

例：

public int sum1(int n) {
   int sum = 0;                            // 执行一次
   for (int i = 1; i <= n; i++) {          // 执行n + 1次
       sum += i;                           // 执行n次
   }
   return sum;
}

public int sum2(int n) {
   int sum = 0;                            // 执行一次
   sum = (1 + n) * n / 2;                  // 执行一次
  return sum;
}

以上为两种求和算法

第一种算法执行了 1 + （n + 1 ）+ n = 2n + 2次
第二种算法执行了 1 + 1 = 2次

如果我们把循环看做一个整体，不考虑判断以及初始化的开销，那么两个算法就是n和1的差距

注：for循环的过程中会先进行判断，才会进入循环体，在最后一次判断并不进入所以为n + 1次，那么为什么不考虑这个判断时间呢，请看下面的例子

int n = 10000;
int x = 0;
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    x++;
    sum = sum + x;
  }
}

这个例子中，外层循环每执行一次，内部循环会执行10000次，而且循环内的逻辑可能会很复杂，在这种情况下，判断的时间是可以忽略不计的

另一方面，我们研究算法的复杂度，侧重的是研究算法随着输入规模扩大增长量的一个抽象，而不是精确的定位需要执行几条指令，如果精确到指令执行条数有需要考虑编译器优化等问题了。所以对于这个例子，我们可以判定需要执行 $n^2$ 次

我们不关心编写程序所用的语言，也不关心程序跑在什么样的机器上，我们只关心他所实现的算法，这样不计循环索引的递增和循环终止条件、变量声明、打印等操作。最终在分析程序运行时间的时候，最重要的就是把程序堪称是独立于程序设计语言的算法或是一系列步骤。我们在分析一个算法的运行时间是，最重要的是 $\color{red}{把基本操作的数量和输入模式关联起来}$