算法时间复杂度

时间复杂度

1. 用于度量某个算法的运算时间，本质是一个函数，在不使用具体测试数据进行测试的情况下，粗略地估计算法的执行效率。
2. 时间复杂度表示的只是代码执行时间随数据规模增长的变化趋势，故也叫作渐进时间复杂度。
3. 时间复杂度常用大Ο来表述。

Ο – 小于等于（常用于计算最坏情况，作为时间复杂度上界）

1. T(n) = Ο(f(n)) 它表示随着输入大小n的增大，算法执行所需时间的增长速度可以用f(n)来描述。其中，T(n)代表算法执行的时间，f(n)代表T(n)的上界，即当n > c (任意常数)，总有T(n) <= f(n)。
2. 插入排序的时间复杂度我们都说是 Ο(n^2), 但在数据本来有序的情况下时间复杂度是 Ο(n)，也就是对于所有 输入情况来说，最坏是 Ο(n^2)的时间复杂度，故称插入排序的时间复杂度为 Ο(n^2)。
3. 快排的时间复杂度是 Ο(nlogn)，但当数据已有序的情况下，快排的时间复杂度是 Ο(n^2)，严格从大Ο的定义来讲，快速排序的时间复杂度应该是 Ο(n^2)，但我们依然说快速排序是 Ο(nlogn)的时间复杂度，这个就是业内的一个默认规定，我们这里说的Ο代表的就是一般情况，不是严格的上界。

常见复杂度量级

求解算法的时间复杂度的具体步骤

1. 找出算法中的基本语句：算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。
2. 计算基本语句的执行次数的数量级：只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂。和最高次幂的系数，这样能够简化算法分析，并且使注意力集中在增长率上。
3. 用大Ο记号表示算法的时间性能：将基本语句执行次数的数量级放入大Ο记号中。

推导时间复杂度的原则

1. 若运行时间是常数量级，则用常数1表示。
2. 只保留时间函数中最高阶项，如Ο(n^2 + 4n)，保留最高阶项后，成为Ο(n^2)。
3. 若最高阶项存在，则省去最高阶项前的系数，如Ο(4n^2)，省去最高阶项的系数后，成为 Ο(n^2)。

分析时间复杂度的方法

1. 只关注循环执行次数最多的一行代码。
2. 加法原则：总复杂度等于量度最大的那段代码的复杂度。
3. 乘法原则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。

O(logn)

1. 一个算法的时间复杂度是logn，可以是以2为底n的对数，也可以是以10为底n的对数，但我们统一说logn，也就是忽略底数的描述。
2. 二分查找
   因为二分查找每次排除掉一半的不适合值，所以对于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)

1. 归并排序
   归并排序递归树是一棵满二叉树，满二叉树的高度大约是 log₂n，故归并排序递归实现的时间复杂度大约是Ο(nlogn)。
2. 将一个复杂度为Ο(logn)的代码重复执行n次，那么此时代码的复杂度就变成了Ο(nlogn)。

       void hello (int n){
           for( int i = 1 ; i < n ; i++){
               int m = 1;
               while( m < n ){
                   m *= 2;
               }
           }
       }
   1
   2
   3
   4
   5
   6
   7
   8

Ο(2^n)

1. 下面的代码有两次递归调用，函数的执行时间就会和输入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);
   	}
   1
   2
   3
   4
   5