一文徹底了解時間復(fù)雜度

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

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

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

那么我們今天先來看看時間復(fù)雜度！

時間復(fù)雜度

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

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

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

找到某條基本語句與問題規(guī)模N之間的數(shù)學(xué)表達式，就算出了該算法的時間復(fù)雜度

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語句執(zhí)行了幾次？

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(xiàn)(N)的結(jié)果就是我們的時間復(fù)雜度。其實并不然，我們并不需要一個精確的運行次數(shù)，只需要知道程序運行次數(shù)的量級就行了

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

2.1大O的漸進表示法

大O符號（Big O notation）：是用于描述函數(shù)漸進行為的數(shù)學(xué)符號

推導(dǎo)大O階方法：

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

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

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

使用這種方法后，test1函數(shù)的時間復(fù)雜度為

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

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

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

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

2.2多種情況取最壞

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

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

平均情況：期望的運行次數(shù)

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

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

最好情況：1次就找到

平均情況：N/2次

最壞情況：N次

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

2.3常見時間復(fù)雜度的計算

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);}

這里出現(xiàn)了兩個循環(huán)，分別是2N次和10次。前面提到了大O漸進法只保留最高階數(shù)并省略系數(shù)，所以它的時間復(fù)雜度是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);}

這里出現(xiàn)了次數(shù)為N和M的兩層循環(huán)：

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

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

一般情況取O(M+N)

NO.3 常數(shù)階

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

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

只要循環(huán)次數(shù)已知，為一常數(shù)且和所傳參數(shù)無關(guān)，其時間復(fù)雜度即為O(1)

NO.4 strchr

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

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

可這里面沒有strchr，但有strstr

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

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

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

打開cplusplus網(wǎng)站，搜索strchr，即可轉(zhuǎn)到函數(shù)定義

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

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

這樣一來，strchr函數(shù)的時間復(fù)雜度就很清楚了，就是遍歷字符串所需要的次數(shù)，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;     }}

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

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

每一次排序都需要遍歷一次數(shù)組

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

能否通過循環(huán)層級判斷？

細心的你可能會發(fā)現(xiàn)，上述代碼中出現(xiàn)了兩層循環(huán)，那是不是可以通過循環(huán)層級來判斷時間復(fù)雜度呢？

并不能！

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

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

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

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;}

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

假設(shè)我們找了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)

通過時間復(fù)雜度的對比，我們就能看出二分查找的優(yōu)勢在那里了

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

NO.7 計算N!

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

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

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

遞歸算法時間復(fù)雜度計算

如果每次函數(shù)調(diào)用是O(1)，看遞歸次數(shù)

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

NO.8 斐波那契數(shù)列

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

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

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

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

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

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

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

NO.9

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

此函數(shù)有一個循環(huán)，但是循環(huán)沒有被執(zhí)行n次，i每次都是2倍進行遞增，所以循環(huán)只會被執(zhí)行l(wèi)og2n次

NO.10

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

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

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

審核編輯：湯梓紅