算法效率的度量方法
比较容易想到的就是我们把算法跑若干次，然后拿计时器在旁边计时，这种方法貌似不错，但是不需真正的计时器来计时，可以利用计算机计时
事后统计法：这种方法主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
但是，这种算法有很大的缺陷：
一、必须依据算法事先编制好的测试程序，通常需要花费大量时间和精力，完了发觉测试的是糟糕的算法，那不是功亏一篑？
二、不同的测试环境差别不是一般的大！
因此这个方法不推荐
为了对算法的评判更为科学和便捷，研究出了事前分析估算的方法
事前估算方法：在计算机编写程序之前，依据统计方法对算法进行估算。
影响算法效率的因素：
1）算法采用的策略，方案
2）编译产生大代码质量
3）问题的输入规模
4）机器执行指令的速度
因此抛开与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。
第一种算法例子：
一共执行了1+1+1+n+1+n = 2n+4次
第二种算法：
一共执行了3次
如果我们把循环看成一个整体，忽略头尾判断的开销，那么这两次算法其实就是n和1的差距。
那循环判断在算法1里边执行了n+1次，看起来是不少的数据量，怎么能说忽略就忽略呢？
请看如下例子：
以上的例子需要执行100^2次。
这嵌套循环，循环条件i从1到100，每次都要让j从1循环到100次，如果非常较真的研究总共精确执行次数，如果数字不凑巧，那是非常累的。
另外，我们研究算法的复杂度，侧重的是研究算法随着输入规模扩大增长量的一个抽象，而不是精确地定位需要执行多少次，因为如果这样的话，我们就又得考虑回编译器的优化问题，然后一直这样没完没了。
我们不关心编写程序所用的语言是什么，也不关心这些程序将跑在什么样的计算机上，我们只关心它所实现的算法。
这样，不计较那些恶循环索引的递增和循环终止条件、变量声明、打印结果等操作。最终，在分析程序的运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。
我们在分析一个算法的运行时间时，重要的是把基本操作的数量和输入模式关联起来。
函数渐进增长
导入：判断以下两个算法A和B哪个更好？
1、假设两个算法的输入规模都是n，算法A要做2n+3次操作，算法B要做3n+1次操作，你觉得哪个更快一点？
规模 |
算法A（2n+3） |
算法A1（2n） |
算法B（3n+1） |
算法B1(3n) |
n = 1 |
5 |
2 |
4 |
3 |
N = 2 |
7 |
4 |
7 |
6 |
N = 3 |
9 |
6 |
10 |
9 |
N = 10 |
23 |
20 |
31 |
30 |
N = 100 |
203 |
200 |
301 |
300 |
解析：当n= 1时，算法A效率不如算法B；当n=2时，两者效率相同；当n>2时，算法A就开始优先于算法B，随着n的增加，算法A比算法B逐步拉大差距。所以总体上算法A比算法B优秀。
函数的渐进增长：给定的两个函数f(n)和g(n),如果存在一个整数N，对于所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的增长渐进快于g(n)。
从刚才的对比可以发现：随着n的增长，后面+1和+3并不影响最终算法的变化曲线的。
例如以上例题中的算法A和算法B，所以我们可以忽略这些加法常数。
2、算法C是4n+8,算法D是2n^2+1
规模 |
算法C(4n+8) |
算法C1(n) |
算法D(2n^2+1) |
算法D1（n^2） |
N = 1 |
12 |
1 |
3 |
1 |
N = 2 |
16 |
2 |
9 |
4 |
N = 3 |
20 |
3 |
19 |
9 |
N = 10 |
48 |
10 |
201 |
100 |
N = 100 |
408 |
100 |
20001 |
10000 |
N = 1000 |
4008 |
1000 |
2000001 |
1000000 |
通过上图可观察发现，当n的值无穷时，哪怕是去掉与n相乘的常数，两者的结果还是没有改变，算法C1随着时间的增长远远小于D1。也就是说，与最高次项相乘的常数并不重要，也可以忽略。
3、算法E是2n^2+3n+1,算法F是2n^3+3n+1
规模 |
算法E（2n^2+3n+1） |
算法E1（n^2） |
算法F（2n^3+3n+1） |
算法F1(n^3) |
N = 1 |
6 |
1 |
6 |
1 |
N = 2 |
15 |
4 |
23 |
8 |
N = 3 |
28 |
9 |
64 |
27 |
N = 10 |
231 |
100 |
2031 |
1000 |
N = 100 |
20301 |
10000 |
2000301 |
1000000 |
这次，我们通过上图发现，最高项的指数大的，函数随着n的增长，结果也会变得增长的特别就快。
4、算法G是2n^2,算法H是3n+1，算法I是2n^2+3n+1
规模 |
算法G（2n^2） |
算法H(3n+1) |
算法I（2n^2+3n+1） |
N = 1 |
2 |
4 |
6 |
N = 2 |
8 |
7 |
15 |
N = 5 |
50 |
16 |
66 |
N = 10 |
200 |
31 |
231 |
N = 100 |
2000 |
301 |
20301 |
N = 1000 |
2000000 |
3001 |
200301 |
N = 10000 |
200000000 |
30001 |
200030001 |
N = 100000 |
20000000000 |
300001 |
20000300001 |
N = 1000000 |
2000000000000 |
3000001 |
2000003000001 |
这组数据很清楚的显示出，当n的值变得非常大的时候，3n+1已经没法和2n^2的结果相比较，最终几乎可以忽略不计，而算法G跟算法I基本已经重合了
于是，我们得到一个结论，判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注最高项的阶数。