# **函数渐近增长:** 分析算法函数增长率是为了体现跟算法函数有关的因素。为算法的复杂度分析做基础。 概念:给定两个函数f(n)和g(n),如果存在一个整数N，使得对于所有的n>0,f(n)总是比g(n)大，那么我们说f(n)的增长渐近 快于g(n)。 概念似乎有点艰涩难懂，那接下来我们做几个测试。 ### **1.测试一:假设四个算法的输入规模都是n:** 1.算法A1要做2n+3次操作，可以这么理解:先执行n次循环，执行完毕后，再有一个n次循环，最后有3次运算; 2.算法A2要做2n次操作; 3.算法B1要做3n+1次操作，可以这个理解:先执行n次循环，再执行一个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逐渐重叠 到一块，所以我们得出结论: **随着输入规模的增大，算法的常数操作可以忽略不计** ### **2.测试二:假设四个算法的输入规模都是n:** 1.算法C1需要做4n+8次操作 2.算法C2需要做n次操作 3.算法D1需要做2n^2次操作 4.算法D2需要做n^2次操作 那么上述算法，哪个更快一些?  通过数据表格，对比算法C1和算法D1: 当输入规模n<=3时，算法C1执行次数多于算法D1，因此算法C1效率低一些; 当输入规模n>3时，算法C1执行次数少于算法D1，因此，算法D2效率低一些， 所以，总体上，算法C1要优于算法D1. 通过折线图，对比对比算法C1和C2: 随着输入规模的增大，算法C1和算法C2几乎重叠 通过折线图，对比算法C系列和算法D系列: 随着输入规模的增大，即使去除n^2前面的常数因子，D系列的次数要远远高于C系列。 因此，可以得出结论: **随着输入规模的增大，与最高次项相乘的常数可以忽略** ### **3.测试三:假设四个算法的输入规模都是n:** 算法E1: 2n^2+3n+1; 算法E2: n^2 算法F1: 2n^3+3n+1 算法F2: n^3   通过数据表格，对比算法E1和算法F1: 当n=1时，算法E1和算法F1的执行次数一样; 当n>1时，算法E1的执行次数远远小于算法F1的执行次数; 所以算法E1总体上是由于算法F1的。 通过折线图我们会看到，算法F系列随着n的增长会变得特块，算法E系列随着n的增长相比较算法F来说，变得比较 慢，所以可以得出结论: **最高次项的指数大的，随着n的增长，结果也会变得增长特别快** ### **4.测试四:假设四个算法的输入规模都是n:** 假设五个算法的输入规模都是n: 算法G: n^3; 算法H: n^2; 算法I: n: 算法J: logn 算法K: 1 那么上述算法，哪个效率更高呢？   通过观察数据表格和折线图，很容易可以得出结论: **算法函数中n最高次幂越小，算法效率越高 ** 总上所述，在我们比较算法随着输入规模的增长量时，可以有以下规则: 1.算法函数中的常数可以忽略; 2.算法函数中最高次幂的常数因子可以忽略; 3.算法函数中最高次幂越小，算法效率越高。