算法中时间复杂度分析

算法的时间复杂度表示算法运行所需要的时间

• 大O表示法
• 递归算法中时间复杂度分析

---

大O表示法

大O表示法 是一种体现算法时间复杂度的记法，如果用n表示数据规模，那么O(f(n)表示算法说需要执行的指令数(消耗的时间)和 f(n) 成正比。大O表示法指出了算法执行的最低上限。(大O表示法的前边省略了一个常数)。

例子：有一个字符数组，将数组中的每一个字符串按照字母排序，再将整个字符串数组按照字典序排序求这个算法的时间复杂度。
分析：假设每个字符串的最大长度是s，字符数组中一共有n个字符串。
* 对于一个字符串来说，进行排序的复杂度是O(s*log s),则整个字符数组的复杂度是O(n*s*log s)
* 对于整个字符串数组排序的复杂度是O(n*log n)，而进行字典排序时每次最多进行s次比较，每次比较都是常数时间，所以复杂度是O(s*n*log n)
* 综上：整个算法的复杂度是O(s*n*(log n +log s)

常见的大O阶有常数阶O(1)，线性阶O(n)，平方阶O(n²)，对数阶O(logn)，nlogn阶O(nlogn)等等。如果有在有相同规模的n，则只保留最高阶，如O(n+n²) = O(n²)。

线性阶

随数据规模n线性增长。如下面的代码：

    for(int i=0;i<n;i++){
    //时间复杂度为O(1)的算法
    ...
    }       

对数阶

接着看如下代码：

int number=1;
while(number<n){
    number=number*2;
    //时间复杂度为O(1)的算法
    ...
}

可以看出上面的代码，随着number每次乘以2后，都会越来越接近n，当number不小于n时就会退出循环。假设循环的次数为X，则由2^x=n得出x=log₂n，因此得出这个算法的时间复杂度为O(logn)。

平方阶

下面的代码是循环嵌套：

for(int i=0;i<n;i++){   
  for(int j=i;j<n;j++){
     //复杂度为O(1)的算法
     ... 
      }
  }

需要注意的是内循环中int j=i，而不是int j=0。当i=0时，内循环执行了n次；i=1时内循环执行了n-1次，当i=n-1时执行了1次，我可以推算出总的执行次数为：

n+(n-1)+(n-2)+(n-3)+……+1 = n²/2+n/2

只保留最高阶，因此保留n²/2，并且去掉这个项的常数，1/2,最终这段代码的时间复杂度为O(n²)。

注意：
1.以下代码的复杂度仍为O(n)，原因是只进行了30*n次基本操作。

for(int i=0;i<n;i++){   
  for(int j=0;j<30;j++){
     //复杂度为O(1)的算法
     ... 
      }
  }

2.以下代码的复杂度仍为O(n*log n)。

for(int i=1;i<n;i +=i){   
  for(int j=0;j<n;j++){
     //复杂度为O(1)的算法
     ... 
      }
  }

以上充分说明，应该时刻关注数据规模，而不是一些形式上的类似。

---

递归算法中时间复杂度分析

递归中进行一次递归调用

如下图所示，该二分查找只进行了一次递归调用。每次调用的复杂度为O(1),递归深度为O(log n),
故整个算法的复杂度为O(log n)。

一般来说,在递归函数中只递归一次递归调用，总体的复杂度为O(每个递归函数的时间复杂度*递归深度)

递归中进行多次递归调用

此时应该关注的是调用次数，如下面代码所示：此时可以通过数递归树上的节点。

比如当n=3时，它的递归树如下图 右半侧，更一般的结论如左半侧所示。

又比如，在归并排序中，排序的数据规模都会减少一半，所以递归深度时log n，但是每层进行排序的数据规模都是n,所以时间复杂度是O(n*log n).