1、两种算法的比较
你知道数学家高斯那个关于1+2+3+…+100的故事吗？
高斯7岁那年开始上学。10岁的时候，一次一位老师想治一治班上的淘气学生，他出了一道数学题，让学生从1＋2＋3……一直加到100为止。他想这道题足够这帮学生算半天的，他也可能得到半天悠闲。谁知，出乎他的意料，刚刚过了一会儿。小高斯就举起手来，说他算完了。老师一看答案，5050，完全正确，老师惊诧不已。问小高斯是怎么算出来的，高斯说，他不是从开始加到末尾，而是先把1和100相加，得到101,再把2和99相加，也得101,最后50和51相加，也得101,这样一共有50个101，结果当然就是5050了，聪明的高斯受到了老师的表扬。
你第一次写1加到100的算法是怎么写的？让我猜猜？
int sum=0;
for(int i=1;i<=100;i++){
sum = sum +i;
}
retrun sum;
在计算机飞快的算力下，得出结果：5050。
但对于高斯来说，神童就是神童，他却给出了另一个更完美的答案：
sum=0,n=100;
sum=(i+n)*n/2
retrun sum;
第一种方法，如果用于计算1加到100，那么就要循环100此，如果计算到一亿，就要循环一亿次，而下面这种方法，不管加到多少，都只需要执行一次就够了！
2、算法效率与度量方法
上面两个算法，我们是如何得知算法二比算法一好的呢？
下面介绍两种算法效率的度量方法。
2.1 事后度量法
事后度量法，顾名思义，就是算法运行结束后，通过算法执行的时间，去判断这个算法的效率怎么样？
听起来挺不错的，但是基本上很少有算法能采用事后度量的方法来评估算法。为什么？
- 需要编制好代码：事后度量法，必须基于运行的代码才能度量，如果度量的结果发现这个算法很糟糕，之前编写的过程基本上就白费了。
- 依赖运行环境：每次度量的结果，很运行算法的计算机状态有很大的关系，不同配置的计算机，比如神威太湖之光和普通的计算机之间运行同一段程序，运行时间差距会很大，就算是同一台计算机，不同时段，计算机CPU和内存占用情况也不相同，容易造成误差。
- 测试数据设计困难：测试一个算法好不好，不是只运行一次就可以了，往往需要很大的测试数据去不断的运行，才能看见他们之间的差距，比如不同的排序算法，对10个数排序，运行结果基本上看不到差异，但要是对100w个数排序，有时间差距就出来了，但是准备100w个数据，就很麻烦。
2.2 事前度量法
事前度量法：在代码编写前，对算法效率进行评估。
厉害吧，代码还没写，就对算法进行评估，怎么做到的呢？
因为对于高级语言编写的程序来说，程序在计算机在运行所消耗的时间取决于以下因素：
- 算法采用的策略方法
- 编译产生的代码质量
- 问题的输入规模
-
机器执行指令的速度
第二条由编译软件来支持，第4条由计算机硬件决定。
所以，除开软硬件的干扰，算法的质量应该取决于：算法的好坏的问题输入的规模。
再看看上面的两种算法
int sum=0; //执行一次
for(int i=1;i<=100;i++){
sum = sum +i; //执行n次
}
retrun sum; //执行1次
第一种算法，一共执行n+2次
那第二种呢？1+1+1=3次
sum=0,n=100; //一次
sum=(i+n)*n/2 //一次
retrun sum; //一次
我们忽略第一行和最后一行相同的代码，这两个算法的执行效率就是1次于n次的差距。高下立见。
3、函数的渐进式增长
如果我们有4个算法，他们的输入都是n,执行次数分别为，2n,2n+3,3n,3n+1,那个算法效率更高？
| n | 2n | 2n+3 | 3n | 3n+1 |
|---|---|---|---|---|
| 1 | 2 | 5 | 3 | 4 |
| 2 | 4 | 7 | 6 | 7 |
| 3 | 6 | 9 | 9 | 10 |
| 10 | 20 | 23 | 30 | 31 |
| 100 | 200 | 203 | 300 | 301 |
| 1000 | 2000 | 2003 | 3000 | 30001 |
发现了什么？在n比较小的时候，4个算法的执行次数其实是差不多的，甚至在n=1的时候，3n和3n+1还比2n+1效率高一些，但随着n的增大，函数2n和2n+3的效率明显好于3n+1。
于是我们得出结论：
算法2n和算法2n+3执行效率上好过算法3n和3n+1
。
在仔细看2n和2n+3,会发现，随着执行次数越大，后面的常数3对整体的执行效率的影响越小，所以我们在得出一个结论：
2n和2n+3算法执行效率相同
。
再来看第二个例子：
一个算法的执行次数是4n+8，一个算法的执行次数是2n
2
+1,他们之间的执行次数是多少？
| n | 4n+8 |
2n 2 +1 |
|---|---|---|
| 1 | 12 | 3 |
| 2 | 16 | 9 |
| 3 | 20 | 19 |
| 10 | 48 | 201 |
| 100 | 408 | 20001 |
| 1000 | 4008 | 2000001 |
随着n的不断变大，两个算法的执行次数差距也越来越大，在仔细观察发现，造成这种差距的原因，都来自于n的平法，而常数2和4对整体的影响远远小于n平方，于是我们再次得出结论：
算法中，与最高次项相乘的函数不重要
。
这又说明了，算法2n和算法3n执行效率可以看作相同的，统一看作n。
最后看一个例子：
一个算法执行次数是2n
2
+3n+1,一个是2n
3
+3n+1,他们的执行次数是
| n |
2n 2 +3n+1 |
2n 3 +3n+1 |
|---|---|---|
| 1 | 6 | 6 |
| 2 | 15 | 23 |
| 3 | 28 | 64 |
| 10 | 231 | 2031 |
| 100 | 2031 | 2000301 |
随着n值的越来越大，后面的3n+1已经对执行次数的影响基本上可以忽略了，所以得出结论：
比较两个算法，只需要比较最高次项就可以了
我们把最后简化的最高次项，记作函数的时间复杂度O。
执行次数2n+1,记作f复杂度O(n).
执行次数2n
2
+n+3,记作时间复杂度O(n
2
)，
而那种没有n的算法，比如第二种计算1加到100的算法，只需执行三次，这种算法的时间复杂度，统一记作O(1)
4、常见的时间复杂度
线性阶
下面的代码，他的时间复杂度为n,因为循环体内要执行n次逻辑代码，这种时间复杂度被称为线性阶。
for(int i=0;i<n;i++){
//执行逻辑代码
}
对数阶
看下面的代码,每次count*2后，都会距离n更近，假设执行x后
2
x
=n,那执行次数x=log
2
n,他的时间复杂度就是O(log
2
n)
int count=1;
while(count<n){
count=count*2;
}
平方阶
这种循环嵌套的，执行次数为n
2
，时间复杂度为n
2
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
//逻辑
}
}
5、最坏情况和最好情况
有时候，我们要在n个数字的随机数组里查找某个数，我们按顺序查，可能第一个数字就是要找的值，时间复杂度O(1)，也可能是最后一个，时间复杂度O(n),我们把第一种情况乘坐最好时间复杂度，而第二种情况称作最坏时间复杂度。而我们评估一个算法时，往往考虑的是最坏1情况，所以，一般在没有做特殊说明的情况下，时间复杂度，都是说的最坏时间复杂度。