时间复杂度
- 用于度量某个算法的运算时间，本质是一个函数，在不使用具体测试数据进行测试的情况下，粗略地估计算法的执行效率。
- 时间复杂度表示的只是代码执行时间随数据规模增长的变化趋势，故也叫作渐进时间复杂度。
- 时间复杂度常用大Ο来表述。
Ο – 小于等于（常用于计算最坏情况，作为时间复杂度上界）
- T(n) = Ο(f(n)) 它表示随着输入大小n的增大，算法执行所需时间的增长速度可以用f(n)来描述。其中，T(n)代表算法执行的时间，f(n)代表T(n)的上界，即当n > c (任意常数)，总有T(n) <= f(n)。
- 插入排序的时间复杂度我们都说是 Ο(n^2), 但在数据本来有序的情况下时间复杂度是 Ο(n)，也就是对于所有 输入情况来说，最坏是 Ο(n^2)的时间复杂度，故称插入排序的时间复杂度为 Ο(n^2)。
- 快排的时间复杂度是 Ο(nlogn)，但当数据已有序的情况下，快排的时间复杂度是 Ο(n^2)，严格从大Ο的定义来讲，快速排序的时间复杂度应该是 Ο(n^2)，但我们依然说快速排序是 Ο(nlogn)的时间复杂度，这个就是业内的一个默认规定，我们这里说的Ο代表的就是一般情况，不是严格的上界。
常见复杂度量级
| 种类 | Ο表示 |
|---|
| 常量阶 | Ο(1) |
| 对数阶 | Ο(logn) |
| 线性阶 | Ο(n) |
| 线性对数阶 | Ο(nlogn) |
| n方阶 | Ο(nⁿ) |
| 指数阶 | Ο(2ⁿ) |
| 阶乘阶 | Ο(n!) |
求解算法的时间复杂度的具体步骤
- 找出算法中的基本语句：算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
- 计算基本语句的执行次数的数量级：只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂。和最高次幂的系数，这样能够简化算法分析，并且使注意力集中在增长率上。
- 用大Ο记号表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。
推导时间复杂度的原则
- 若运行时间是常数量级，则用常数1表示。
- 只保留时间函数中最高阶项，如Ο(n^2 + 4n)，保留最高阶项后，成为Ο(n^2)。
- 若最高阶项存在，则省去最高阶项前的系数，如Ο(4n^2)，省去最高阶项的系数后，成为 Ο(n^2)。
分析时间复杂度的方法
- 只关注循环执行次数最多的一行代码。
- 加法原则：总复杂度等于量度最大的那段代码的复杂度。
- 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
O(logn)
- 一个算法的时间复杂度是logn，可以是以2为底n的对数，也可以是以10为底n的对数，但我们统一说logn，也就是忽略底数的描述。
- 二分查找
因为二分查找每次排除掉一半的不适合值，所以对于n个元素的情况：
1次二分剩下：n/2
2次二分剩下：n/2/2 = n/4
…
m次二分剩下：n/(2^m)
最坏的情况下，m次二分后只剩下最后一个值，则 n/(2^m) = 1 => 2^m = n => m = log₂n
故时间复杂度为：Ο(logn)
Ο(nlogn)
- 归并排序
归并排序递归树是一棵满二叉树，满二叉树的高度大约是log2n，故归并排序递归实现的时间复杂度大约是Ο(nlogn)。 - 将一个复杂度为Ο(logn)的代码重复执行n次，那么此时代码的复杂度就变成了Ο(nlogn)。
void hello (int n){
for( int i = 1 ; i < n ; i++){
int m = 1;
while( m < n ){
m *= 2;
}
}
}
Ο(2^n)
- 下面的代码有两次递归调用，函数的执行时间就会和输入n成指数的关系。
// f(n) = 2^0 + 2^1 + 2^2 + ... + 2^n = 2^(n+1)
int func(int n){
if(n==0) return 1;
return func(n) + func(n-1);
}
