冰与火之歌：「时间」与「空间」复杂度 (2)

 

1void selectionSort(int arr[],int n){
2   for(int i = 0; i < n ; i++){
3     int minIndex = i;
4     for (int j = i + 1; j < n ; j++ )
5       if (arr[j] < arr[minIndex])
6           minIndex = j;
7
8     swap ( arr[i], arr[minIndex]);
9   }
10}

这里简单的推导一下

当 i = 0 时，第二重循环需要运行 (n - 1) 次

当 i = 1 时，第二重循环需要运行 (n - 2) 次

。。。。。。

不难得到公式：

1(n - 1) + (n - 2) + (n - 3) + ... + 0
2= (0 + n - 1) * n / 2
3= O (n ^2)

当然并不是所有的双重循环都是 O(n²)，比如下面这段输出 30n 次 Hello,五分钟学算法：）的代码。

1void printInformation (int n ){
2   for (int i = 1 ; i <= n ; i++)
3        for (int j = 1 ; j <= 30 ; j ++)
4           cout<< "Hello,五分钟学算法：）"<< endl;
5}
O(logn)

1int binarySearch( int arr[], int n , int target){
2  int l = 0, r = n - 1;
3  while ( l <= r) {
4    int mid = l + (r - l) / 2;
5    if (arr[mid] == target) return mid;
6    if (arr[mid] > target ) r = mid - 1;
7    else l = mid + 1;
8  }
9  return -1;
10}

在二分查找法的代码中，通过while循环，成 2 倍数的缩减搜索范围，也就是说需要经过 log2^n 次即可跳出循环。

同样的还有下面两段代码也是 O(logn) 级别的时间复杂度。

1  // 整形转成字符串
2  string intToString ( int num ){
3   string s = "";
4   // n 经过几次“除以10”的操作后，等于0
5   while (num ){
6    s += '0' + num%10;
7    num /= 10;
8   }
9   reverse(s)
10   return s;
11  }
1void hello (int n ) {
2   // n 除以几次 2 到 1
3   for ( int sz = 1; sz < n ; sz += sz) 
4     for (int i = 1; i < n; i++)
5        cout<< "Hello,五分钟学算法：）"<< endl;
6}
O(nlogn)

将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logn)，也就是了O(nlogn)。

1void hello (){
2  for( m = 1 ; m < n ; m++){
3    i = 1;
4    while( i < n ){
5        i = i * 2;
6    }
7   }
8}
不常见的时间复杂度

下面来分析一波另外几种复杂度： 递归算法的时间复杂度（recursive algorithm time complexity），最好情况时间复杂度（best case time complexity）、最坏情况时间复杂度（worst case time complexity）、平均时间复杂度（average case time complexity）和均摊时间复杂度（amortized time complexity）。

递归算法的时间复杂度

如果递归函数中，只进行一次递归调用，递归深度为depth；

在每个递归的函数中，时间复杂度为T；

则总体的时间复杂度为O(T * depth)。