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/2retrun sum;

第一种方法，如果用于计算1加到100，那么就要循环100此，如果计算到一亿，就要循环一亿次，而下面这种方法，不管加到多少，都只需要执行一次就够了！

2、算法效率与度量方法

上面两个算法，我们是如何得知算法二比算法一好的呢？
下面介绍两种算法效率的度量方法。

2.1 事后度量法

事后度量法，顾名思义，就是算法运行结束后，通过算法执行的时间，去判断这个算法的效率怎么样？

听起来挺不错的，但是基本上很少有算法能采用事后度量的方法来评估算法。为什么？

• 需要编制好代码：事后度量法，必须基于运行的代码才能度量，如果度量的结果发现这个算法很糟糕，之前编写的过程基本上就白费了。
• 依赖运行环境：每次度量的结果，很运行算法的计算机状态有很大的关系，不同配置的计算机，比如神威太湖之光和普通的计算机之间运行同一段程序，运行时间差距会很大，就算是同一台计算机，不同时段，计算机CPU和内存占用情况也不相同，容易造成误差。
• 测试数据设计困难：测试一个算法好不好，不是只运行一次就可以了，往往需要很大的测试数据去不断的运行，才能看见他们之间的差距，比如不同的排序算法，对10个数排序，运行结果基本上看不到差异，但要是对100w个数排序，有时间差距就出来了，但是准备100w个数据，就很麻烦。

2.2 事前度量法

事前度量法：在代码编写前，对算法效率进行评估。
厉害吧，代码还没写，就对算法进行评估，怎么做到的呢？
因为对于高级语言编写的程序来说，程序在计算机在运行所消耗的时间取决于以下因素：

1. 算法采用的策略方法
2. 编译产生的代码质量
3. 问题的输入规模
4. 机器执行指令的速度
   第二条由编译软件来支持，第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比较小的时候，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²+1,他们之间的执行次数是多少？

随着n的不断变大，两个算法的执行次数差距也越来越大，在仔细观察发现，造成这种差距的原因，都来自于n的平法，而常数2和4对整体的影响远远小于n平方，于是我们再次得出结论：算法中，与最高次项相乘的函数不重要。
这又说明了，算法2n和算法3n执行效率可以看作相同的，统一看作n。
最后看一个例子：
一个算法执行次数是2n²+3n+1,一个是2n³+3n+1,他们的执行次数是

随着n值的越来越大，后面的3n+1已经对执行次数的影响基本上可以忽略了，所以得出结论：比较两个算法，只需要比较最高次项就可以了
我们把最后简化的最高次项，记作函数的时间复杂度O。
执行次数2n+1,记作f复杂度O(n).
执行次数2n²+n+3,记作时间复杂度O(n²)，
而那种没有n的算法，比如第二种计算1加到100的算法，只需执行三次，这种算法的时间复杂度，统一记作O(1)

4、常见的时间复杂度

线性阶

下面的代码，他的时间复杂度为n,因为循环体内要执行n次逻辑代码，这种时间复杂度被称为线性阶。

for(int i=0;i<n;i++){//执行逻辑代码}

对数阶

看下面的代码,每次count*2后，都会距离n更近，假设执行x后
2^x=n,那执行次数x=log₂n,他的时间复杂度就是O(log₂n)

int count=1;while(count<n){    count=count*2;}

平方阶

这种循环嵌套的，执行次数为n²，时间复杂度为n²

for(int i=0;i<n;i++){    for(int j=0;j<n;j++){     //逻辑    }}

5、最坏情况和最好情况

有时候，我们要在n个数字的随机数组里查找某个数，我们按顺序查，可能第一个数字就是要找的值，时间复杂度O(1)，也可能是最后一个，时间复杂度O(n),我们把第一种情况乘坐最好时间复杂度，而第二种情况称作最坏时间复杂度。而我们评估一个算法时，往往考虑的是最坏1情况，所以，一般在没有做特殊说明的情况下，时间复杂度，都是说的最坏时间复杂度。