博客

2.2 函数渐近增长（用来推理大O表示法）

概念：

给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是 比 g(n)大，那么我们说 f(n) 的增长渐近快于g（n）。（f比g效率要低）

测试①：

假设四个算啊的输入规模都是n：

1. 算法A1 要做 2n +3 次操作，可以这么理解：先执行 n 次的循环，执行完毕后，再有一个n次循环，最后有三次运算。
2. 算法A2 要做 2n 次操作
3. 算法B1 要做 3n + 1 次的操作，可以这个理解：先执行 n 次循环，再执行一个 n 次的循环，最后有一个 1 次的运算。
4. 算法B2 要做 3n次 的操作

那么上述的算法，哪个更快一些呢？

从上述表格可以观察出下面的图示：



通过数据表格，比较算法A1和算法B1：

• 当输入规模n=1时，A1需要执行5次，B1需要执行4次，所以A1的效率比B1的效率低。
• 当输入规模n=2时，A1需要执行7次，B1需要执行7次，所以A1的效率和B1的效率一样。
• 当输入规模n>2时，A1需要的执行次数一直比B1需要执行的次数少，所以A1的效率比B1的效率高。
  
  所以我们可以得出结论：

当输入规模 n > 2 时，算法A1的渐近增长小于算法B1的渐近增长

但是！！通过观察折线图，我们发现，随着输入规模的增大，算法A1和算法A2逐渐重叠到一块儿了，算法B1和算法B2逐渐也重叠在一起，所以我们得出结论。

随着输入规模的增大，算法的常数操作是可以忽略不计的！

测试②：

假设四个算法的输入规模都是n：

1. 算法C1需要做 4n + 8 次操作
2. 算法C2需要做 n 次操作
3. 算法D1需要做 2n
   
   ²
   
   次操作
4. 算法D2需要做 n
   
   ²
   
   次操作

那么上述算法，哪个更快一些？

从上述表格可以观察出下面的图示：



这个 图 其实 取值 是段落的，所以看不出来。其实 C1和C2的曲线 在 n 逐渐变大的时候 已经 趋于 重合了，包括 D1 和 D2。

通过数据表格，比较算法C1和算法D1：

• 当输入规模 n <= 3 时，算法C1执行次数多于 算法 D1，因此算法 C1 效率低一些;
• 当输入规模 n > 3 时，算法C1执行次数少于 算法 D1，因此，算法 D2 效率低一些;
• 所以总体上来说，算法 C1 优于 算法 D1 的。

通过折线图，对比对比算法C1和算法C2：

• 随着输入规模的增大，算法C1和算法C2几乎重叠

通过折线图，对比算法 C系列和算法D系列：

• 
  随着输入规模的增大，即使去除 n
  
  ²
  
  前面的常数因子,D系列 的次数也是要 远远高于 C系列的。
  

• 
  
  随着输入规模的增大，与最高次项相乘的常数可以忽略！
  
  

测试③：

假设四个算法的输入规模都是n：

1. 算法E1：2n
   
   ²
   
   +3n+1
2. 算法E2：n
   
   ²
   
3. 算法F1：2n^3+3n+1
4. 算法F2：n
   
   ³
   

那么上述算法，哪个更快一些？

从上述表格可以观察出下面的图示：



通过数据表格，对比算法E1和算法F1：

当 n = 1时，算法E1 和 算法 F1 的执行次数一样;

当 n > 1时，算法E1的执行次数云云小于算法F1的执行次数;

所以算法E1总体上是由于算法F1的。

通过折线图我们会看到，算法 F 系列 随着 n 的 增长 会变得特快，算法 E 系列随着 n 的增长 相比较算法 F 来说，变得 比较慢，所以 可以得出结论：

最高次项的指数大的，随着 n 的增长，结果也会变得增长特别快。

测试④：

假设五个算法的输入规模都是 n ：

1. 算法G：n
   
   ³
   
2. 算法H：n
   
   ²
   
3. 算法I：n
4. 算法J：log
   
   _n
   
5. 算法K：1

那么上述算法，哪个更快一些？

从上述表格可以观察出下面的图示：



通过观察数据表格和折线图，很容易可以的得出结论：

算法函数中 n 最高次幂越小，算法效率越高

综上所述，在我们比较算法随着输入规模的增长量时，可以有以下规则：

1.** 算法函数中的常数可以忽略;**

2.

算法函数中最高次幂的常数银子可以忽略;


3.** 算法函数中最高次幂越小，算法效率越高;**