Question

快速理解算法时间复杂度

Answer 1

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

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

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

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

存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(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等算法，可以 参考皇叔的博客