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

時(shí)間復(fù)雜度：衡量一個(gè)算法的運(yùn)行速度

空間復(fù)雜度：衡量一個(gè)算法運(yùn)行需要開(kāi)辟的額外空間

那么我們今天先來(lái)看看時(shí)間復(fù)雜度！

時(shí)間復(fù)雜度

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

時(shí)間復(fù)雜度是一個(gè)近似值，并不是實(shí)際運(yùn)行的時(shí)間

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

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

請(qǐng)問(wèn)這個(gè)代碼中，count語(yǔ)句執(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

你可能會(huì)簡(jiǎn)單地認(rèn)為，F(xiàn)(N)的結(jié)果就是我們的時(shí)間復(fù)雜度。其實(shí)并不然，我們并不需要一個(gè)精確的運(yùn)行次數(shù)，只需要知道程序運(yùn)行次數(shù)的量級(jí)就行了

這里我們使用大O漸進(jìn)表示法來(lái)表示時(shí)間復(fù)雜度（空間復(fù)雜度同理）

2.1大O的漸進(jìn)表示法

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

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

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

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

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

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

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

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

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

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

2.2多種情況取最壞

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

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

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

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

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

????????最好情況：1次就找到

????????平均情況：N/2次

????????最壞情況：N次

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

2.3常見(jiàn)時(shí)間復(fù)雜度的計(jì)算

NO.1

這里出現(xiàn)了兩個(gè)循環(huán)，分別是2N次和10次。前面提到了大O漸進(jìn)法只保留最高階數(shù)并省略系數(shù)，所以它的時(shí)間復(fù)雜度是O(N)

NO.2

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

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

當(dāng)M遠(yuǎn)遠(yuǎn)大于N時(shí)，時(shí)間復(fù)雜度為O(M)

一般情況取O(M+N)

NO.3 常數(shù)階

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

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

NO.4 strchr

看到這道題的時(shí)候，你可能會(huì)一愣，strchr是什么？

可這里面沒(méi)有strchr，但有strstr

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

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

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

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

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

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

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

NO.5 冒泡排序

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

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

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

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

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

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

并不能！

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

我們要準(zhǔn)確分析算法的思路，并不能簡(jiǎn)單地通過(guò)循環(huán)層級(jí)來(lái)判斷時(shí)間復(fù)雜度

NO.6 二分查找

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

假設(shè)我們找了x次，每一次查找都會(huì)使查找范圍減半

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)

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

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

NO.7 計(jì)算N!

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

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

遞歸算法時(shí)間復(fù)雜度計(jì)算

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

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

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

每次遞歸，次數(shù)都會(huì)增加，總的來(lái)說(shuō)是以2^x的量級(jí)增加的（x代表行數(shù)）

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

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

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

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

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

NO.9

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

NO.10

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

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

-----------------------------------

51CTO丨作者：慕雪年華

為了幫助大家，輕松，高效學(xué)習(xí)C語(yǔ)言/C++,給大家分享我收集的資源，從最零基礎(chǔ)開(kāi)始的,幫助大家在學(xué)習(xí)C語(yǔ)言的道路上披荊斬棘！

微信公眾號(hào)：C語(yǔ)言編程學(xué)習(xí)基地

C語(yǔ)言零基礎(chǔ)入門教程（83集全）

整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門教程）最重要的是你可以在群里面交流提問(wèn)編程問(wèn)題哦！

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！大家也要把握住有限的時(shí)光，抓住成長(zhǎng)的每一次機(jī)會(huì)哦~

編程學(xué)習(xí)書(shū)籍分享：

粉絲編程交流：