看动画轻松理解时间复杂度（一） (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}

更多复杂度分析内容可以在公众号 五分钟学算法 获取