快速理解算法时间复杂度

算法在移动端开发中用到的并不多但是在面试时面试官为了试探你的水平经常会问到。这块在大学的时候数据结构那门课中讲的挺多的，各种排序，查找算法的时间复杂度，当时理解的不够好所以再来学习下。

一个程序执行的的时间是需要通过上机来确定的而且你取决于你的CPU的运算能力，时间复杂度只是在算法中进行的横向对比不代表具体的时间。

1、时间频度：一个算法中的语句执行次数称为语句频度或时间频度记作：T(N)

int test(void) {
    printf("Hello, World!\n");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

这个test类的时间频度为T(2)

int aFunc(int n) {
    for(int i = 0; i<n; i++) {         // 需要执行 (n + 1) 次
        printf("Hello, World!\n");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

这个时间频度为n+1+n+1也就是T(2n+2)
时间频度这个概念还是比较好理解的就是数一下当前程序所有的语句每一句语句加起来一共执行了多少次。

开始引入时间复杂度的概念

存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。
如图：

时间复杂度示意图
直线为T(n)=2n+2,曲线为f(n)=n^2
对图中的两条线进行解释：当n=2是T(n)=f(n)则称这个使f(n)=T(n)的这个n值2为C，当n>C时f(n)的增长速度永远大于T(n)也就是f(n)是T(n)的上界。则可以表示为 T(n) = O(f(n))。

时间复杂度怎么计算：

本文开始的两个例子：
1、T(n)=2则f(n)=2所以可以推算出O(f(n))=O(2)(这样表示并不正确下面会解释)
2、T(n)=2n+2所以可以推算出O(f(n))=O(2n+2)(这样表示并不正确下面会解释)

上面的这两个例子的表示方法为什么不不正确的呢？从时间复杂度的定义可以看出来大O的表示法是一个极值或者说是一个不准确的值它只是表示了T(n)的变化速率所以说大O推导出来大O还需要一些方法，一共三种:

1.用常数1来取代运行时间中所有加法常数。
2.修改后的运行次数函数中，只保留最高阶项
3.如果最高阶项存在且不是1，则去除与这个项相乘的常数。

从这三条规律可以得出第一个应该是O(1)，第二个应该是O(2n)，当然还有logn,n^2等算法，可以参考皇叔的博客