算法在編寫成可執行程序的時候，main函數使用這個算法，需要調用一定的空間，消耗一定的時間。算法的效率就是通過空間和時間這兩個維度來評判的。

時間復雜度：衡量一個算法的運行速度

空間復雜度：衡量一個算法運行需要開辟的額外空間

那么我們今天先來看看時間復雜度！

時間復雜度

算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。算法中基本操作的執行次數，為算法的時間復雜度

時間復雜度是一個近似值，并不是實際運行的時間

實際上代碼的運行時間，和機器的內存、cpu性能和平臺都有關系，同一個代碼在不同的機器上運行時間都不一樣，如果只以純粹的時間來考核，很難分析

找到某條基本語句與問題規模N之間的數學表達式，就算出了該算法的時間復雜度

void Test(int N){    int count =0;    for(int i=0;i    {        for(int j=0;j        {            count++;        }    }        for (int k = 0; k < 2 * N ; ++ k)    {        count++;    }        int M = 10;    while (M--)    {        count++;    }        return;}

請問這個代碼中，count語句執行了幾次？

F ( N ) = N 2 + 2 ? N + 10 F(N)=N^2+2*N+10 F(N)=N2+2?N+10

N = 10 F(N) = 130

N = 100 F(N) = 10210

N = 1000 F(N) = 1002010

你可能會簡單地認為，F(N)的結果就是我們的時間復雜度。其實并不然，我們并不需要一個精確的運行次數，只需要知道程序運行次數的量級就行了

這里我們使用大O漸進表示法來表示時間復雜度（空間復雜度同理）

2.1大O的漸進表示法

大O符號（Big O notation）：是用于描述函數漸進行為的數學符號

推導大O階方法：

（1）用常數1取代運行時間中的所有加法常數。

（2）在修改后的運行次數函數中，只保留最高階項。

（3）如果最高階項存在且不是1，則去除與這個項目相乘的常數。得到的結果就是大O階

使用這種方法后，test1函數的時間復雜度為

O ( N 2 ) O(N^2) O(N2)

對于test1函數，在計算的時候，我們省略了最后的+10，保留了最高階數N2，即得出了它的時間復雜度

如果最高階數前面有系數，如2N，系數也將被省略

因為當N的數值很大的時候，后面的那些值對我們總運行次數的影響已經非常小了。大O的漸進表示法去掉了那些對結果影響不大的項，簡潔明了的表示出了執行次數

2.2多種情況取最壞

一些算法的時間復雜度會有最好、最壞和平均的情況

最好情況：任意輸入規模的最小運行次數(下界)

平均情況：期望的運行次數

最壞情況：任意輸入規模的最大運行次數(上界)

舉個例子，當我們編寫一個在數組中查找數值的算法時，它可能會出現這幾種情況：

最好情況：1次就找到

平均情況：N/2次

最壞情況：N次

在實際中的一般情況，我們關注的是算法的最壞運行情況，所以數組中搜索數據時間復雜度為O(N)

2.3常見時間復雜度的計算

NO.1

void Func1(int N){     int count = 0;     for (int k = 0; k < 2 * N ; ++ k)     {      ++count;     }     int M = 10;     while (M--)     {      ++count;     }  printf("%d
", count);}

這里出現了兩個循環，分別是2N次和10次。前面提到了大O漸進法只保留最高階數并省略系數，所以它的時間復雜度是O(N)

NO.2

void Func2(int N, int M){     int count = 0;     for (int k = 0; k < M; ++ k)     {      ++count;     }     for (int k = 0; k < N ; ++ k)     {      ++count;     }     printf("%d
", count);}

這里出現了次數為N和M的兩層循環：

當M和N差不多大的時候，時間復雜度可以理解為O(M)或O(N)

當M遠遠大于N時，時間復雜度為O(M)

一般情況取O(M+N)

NO.3 常數階

void Func3(int N){     int count = 0;     for (int k = 0; k < 100; ++ k)     {      ++count;     }     printf("%d
", count);}

這里我們得知了具體的循環次數為100，是一常數，時間復雜度為O(1)，代表常數階

只要循環次數已知，為一常數且和所傳參數無關，其時間復雜度即為O(1)

NO.4 strchr

//計算strchr的時間復雜度const char * strchr ( const char * str, int character );

看到這道題的時候，你可能會一愣，strchr是什么？

可這里面沒有strchr，但有strstr

strstr函數的作用：在字符串1中尋找是否有字符串2

其中第二個str代表的是string字符串，那我們是不是可以猜想，chr代表的是char字符，其作用是在一個字符串中查找是否有一個字符呢？

當然，光是猜想肯定是不夠的，我們還需要求證一下

打開cplusplus網站，搜索strchr，即可轉到函數定義

可以看到，該函數的作用是定位字符串中第一次出現該字符的位置，返回值是一個pointer指針

和我們猜想的一樣，它的作用就是在字符串中查找一個字符，并返回它第一次出現的位置的地址。

這樣一來，strchr函數的時間復雜度就很清楚了，就是遍歷字符串所需要的次數，O(N)

NO.5 冒泡排序

voidBubbleSort(int*a,intn){     assert(a);     for (size_t end = n; end > 0; --end)     {         int exchange = 0;         for (size_t i = 1; i < end; ++i)         {          if (a[i-1] > a[i])          {                Swap(&a[i-1], &a[i]);                exchange = 1;          }       }     if (exchange == 0)       break;     }}

冒泡排序是一個非常經典的代碼，其思路就是遍歷整個數組，如果待排序數字大于它的下一位，則交換這兩個數字

N個數字的數組需要N-1次排序才能完成

每一次排序都需要遍歷一次數組

這樣算來，冒泡排序的循環次數就是兩個N，即為O(N2)

能否通過循環層級判斷？

細心的你可能會發現，上述代碼中出現了兩層循環，那是不是可以通過循環層級來判斷時間復雜度呢？

并不能！

for(int i=0;i{  for(int j=0;j<3;j++)    printf("hehe
");}

如果是上述這種兩次循環的情況，會打印3n次呵呵，其時間復雜度是O(N)而不是N2

我們要準確分析算法的思路，并不能簡單地通過循環層級來判斷時間復雜度

NO.6 二分查找

intBinarySearch(int*a,intn,intx){assert(a);intbegin=0;intend=n-1;while(beginend){intmid=begin+((end-begin)>>1);//使用位移操作符來模擬/2，防止begin和end相加后超出int范圍if(a[mid]begin=mid+1;elseif(a[mid]>x)end=mid;elsereturnmid;}return-1;}

二分查找的思路這里不再贅述

假設我們找了x次，每一次查找都會使查找范圍減半

N/2/2/2/2 ……

最后我們可以得出2條公式

2 x = N 2^x=N 2x=N

x = l o g 2 N x=log_2N x=log2N

最好情況：O(1)

最壞情況：O(logN)

通過時間復雜度的對比，我們就能看出二分查找的優勢在那里了

可以看到，當數據很大的時候，O(logN)的算法執行次數比O(N)少了特別多!!（來自BT-7274的肯定）

NO.7 計算N!

// 計算階乘遞歸Fac的時間復雜度？long long Fac(size_t N){     if(0 == N)      return 1;
     return Fac(N-1)*N;}

對于這個階乘的遞歸函數而言，每次函數調用是O(1)，時間復雜度主要看遞歸次數

對于數字N而言，遞歸需要N次，時間復雜度是O(N)

遞歸算法時間復雜度計算

如果每次函數調用是O(1)，看遞歸次數

每次函數調用不是O(1)，那么就看他遞歸調用中次數的累加

NO.8 斐波那契數列

// 計算斐波那契遞歸Fib的時間復雜度？long long Fib(size_t N){     if(N < 3)      return 1;
     return Fib(N-1) + Fib(N-2);}

每次遞歸，次數都會增加，總的來說是以2^x的量級增加的（x代表行數）

1 + 2 + 4 + 8 + … … + 2 X ? 2 1+2+4+8+……+2^{X-2} 1+2+4+8+……+2X?2

這里一共有x-1項，用等比數列的求和公式得出，結果為2x-1

所以最后得出的時間復雜度為O(2N)

需要注意的是，當遞歸調用到底部時，有一些調用會較早退出，這部分位于金字塔的右下角

由于時間復雜度只是一個估算值，這一部分缺失的調用次數對總運行次數的影響不大，故忽略掉

NO.9

void fun(int n) {   int i=l;   while(i<=n)      i=i*2;}

此函數有一個循環，但是循環沒有被執行n次，i每次都是2倍進行遞增，所以循環只會被執行log2n次

NO.10

給定一個整數sum，從有N個有序元素的數組中尋找元素a，b，使得a+b的結果最接近sum，最快的平均時間復雜度是？

A. O(n)//√B. O(n^2)C. O(nlogn)D. O(logn)

數組元素有序，所以a,b兩個數可以分別從開始和結尾處開始搜，根據首尾元素的和是否大于sum,決定搜索的移動，整個數組被搜索一遍，就可以得到結果，所以最好時間復雜度為n

審核編輯：湯梓紅