計(jì)算復(fù)雜度和時(shí)間復(fù)雜度（計(jì)算復(fù)雜度和時(shí)間復(fù)雜度的公式）

大家好！今天讓創(chuàng)意嶺的小編來(lái)大家介紹下關(guān)于計(jì)算復(fù)雜度和時(shí)間復(fù)雜度的問(wèn)題，以下是小編對(duì)此問(wèn)題的歸納整理，讓我們一起來(lái)看看吧。

開(kāi)始之前先推薦一個(gè)非常厲害的Ai人工智能工具，一鍵生成原創(chuàng)文章、方案、文案、工作計(jì)劃、工作報(bào)告、論文、代碼、作文、做題和對(duì)話答疑等等

只需要輸入關(guān)鍵詞，就能返回你想要的內(nèi)容，越精準(zhǔn)，寫(xiě)出的就越詳細(xì)，有微信小程序端、在線網(wǎng)頁(yè)版、PC客戶端

官網(wǎng)：https://ai.de1919.com。

創(chuàng)意嶺作為行業(yè)內(nèi)優(yōu)秀的企業(yè)，服務(wù)客戶遍布全球各地，如需了解SEO相關(guān)業(yè)務(wù)請(qǐng)撥打電話175-8598-2043，或添加微信：1454722008

本文目錄:

• 1、時(shí)間復(fù)雜度怎么算

• 2、時(shí)間復(fù)雜度怎么算

• 3、一文講透算法中的時(shí)間復(fù)雜度和空間復(fù)雜度計(jì)算方式

• 4、究竟什么是時(shí)間復(fù)雜度，怎么求時(shí)間復(fù)雜度，看這一篇就夠了

一、時(shí)間復(fù)雜度怎么算

問(wèn)題一：請(qǐng)問(wèn)算法的時(shí)間復(fù)雜度是怎么計(jì)算出來(lái)的? 首先假設(shè)任意一個(gè)簡(jiǎn)單運(yùn)算的時(shí)間都是1，例如a=1;a++;a=a*b;這些運(yùn)算的時(shí)間都是1.

那么例如

for(int i=0;i 問(wèn)題二：數(shù)據(jù)結(jié)構(gòu)中的時(shí)間復(fù)雜度怎么算??？看不懂啊，有沒(méi)有具體的公式 求時(shí)間復(fù)雜度，其實(shí)是在統(tǒng)計(jì)基本操作步驟的執(zhí)行次數(shù)。

“基本操作步驟”指的是加減乘除這種。比如有一個(gè)for循環(huán)，執(zhí)行N次，每次做一個(gè)加法一個(gè)乘法，那么總的操作步驟數(shù)就是2N，用大O記號(hào)就是O(N).

原理就是這么簡(jiǎn)單，計(jì)數(shù)而已。

實(shí)際做題的時(shí)候，看清楚for循環(huán)的嵌套層數(shù)，就差不離。

問(wèn)題三：如何計(jì)算算法的時(shí)間復(fù)雜度 求解算法的時(shí)間復(fù)雜度的具體步驟是：⑴找出算法中的基本語(yǔ)句；算法中執(zhí)行次數(shù)最多的那條語(yǔ)句就是基本語(yǔ)句，通常是最內(nèi)層循環(huán)的循環(huán)體。⑵計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)的數(shù)量級(jí)；只需計(jì)算基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)，這就意味著只要保證基本語(yǔ)句執(zhí)行次數(shù)的函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡(jiǎn)化算法分析，并且使注意力集中在最重要的一點(diǎn)上：增長(zhǎng)率。⑶用大Ο記號(hào)表示算法的時(shí)間性能。將基本語(yǔ)句執(zhí)行次數(shù)的數(shù)量級(jí)放入大Ο記號(hào)中。如果算法中包含嵌套的循環(huán)，則基本語(yǔ)句通常是最內(nèi)層的循環(huán)體，如果算法中包含并列的循環(huán)，則將并列循環(huán)的時(shí)間復(fù)雜度相加。例如：for(i=1;i 問(wèn)題四：如何計(jì)算時(shí)間復(fù)雜度 如何計(jì)算時(shí)間復(fù)雜度

定義：如果一個(gè)問(wèn)題的規(guī)模是n，解這一問(wèn)題的某一算法所需要的時(shí)間為T(mén)(n)，它是n的某一函數(shù) T(n)稱(chēng)為這一算法的“時(shí)間復(fù)雜性”。

當(dāng)輸入量n逐漸加大時(shí)，時(shí)間復(fù)雜性的極限情形稱(chēng)為算法的“漸近時(shí)間復(fù)雜性”。

我們常用大O表示法表示時(shí)間復(fù)雜性，注意它是某一個(gè)算法的時(shí)間復(fù)雜性。大O表示只是說(shuō)有上界，由定義如果f(n)=O(n)，那顯然成立f(n)=O(n^2)，它給你一個(gè)上界，但并不是上確界，但人們?cè)诒硎镜臅r(shí)候一般都習(xí)慣表示前者。

此外，一個(gè)問(wèn)題本身也有它的復(fù)雜性，如果某個(gè)算法的復(fù)雜性到達(dá)了這個(gè)問(wèn)題復(fù)雜性的下界，那就稱(chēng)這樣的算法是最佳算法。

“大 O記法”：在這種描述中使用的基本參數(shù)是 n，即問(wèn)題實(shí)例的規(guī)模，把復(fù)雜性或運(yùn)行時(shí)間表達(dá)為n的函數(shù)。這里的“O”表示量級(jí) (order)，比如說(shuō)“二分檢索是 O(logn)的”,也就是說(shuō)它需要“通過(guò)logn量級(jí)的步驟去檢索一個(gè)規(guī)模為n的數(shù)組”記法 O ( f(n) )表示當(dāng) n增大時(shí)，運(yùn)行時(shí)間至多將以正比于 f(n)的速度增長(zhǎng)。

這種漸進(jìn)估計(jì)對(duì)算法的理論分析和大致比較是非常有價(jià)值的，但在實(shí)踐中細(xì)節(jié)也可能造成差異。例如，一個(gè)低附加代價(jià)的O(n2)算法在n較小的情況下可能比一個(gè)高附加代價(jià)的 O(nlogn)算法運(yùn)行得更快。當(dāng)然，隨著n足夠大以后，具有較慢上升函數(shù)的算法必然工作得更快。

O(1)

Temp=i;i=j;j=temp;

以 上三條單個(gè)語(yǔ)句的頻度均為1，該程序段的執(zhí)行時(shí)間是一個(gè)與問(wèn)題規(guī)模n無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。如果算法的執(zhí)行時(shí) 間不隨著問(wèn)題規(guī)模n的增加而增長(zhǎng)，即使算法中有上千條語(yǔ)句，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。此類(lèi)算法的時(shí)間復(fù)雜度是O(1)。

O(n^2)

2.1. 交換i和j的內(nèi)容

sum=0； （一次）

for(i=1;i>

問(wèn)題五：時(shí)間復(fù)雜度如何計(jì)算 10分 給我十分，我告訴你答案

問(wèn)題六：C語(yǔ)言算法的時(shí)間復(fù)雜度如何計(jì)算?。? 看看這個(gè) 每個(gè)循環(huán)都和上一層循環(huán)的參數(shù)有關(guān)。 所以要用地推公式： 設(shè)i(n)表示第一層循環(huán)的i為n時(shí)的循環(huán)次數(shù)，注意到他的下一層循環(huán)次數(shù)剛好就是n，分別是0,1,2...n-1 所以，把每一層循環(huán)設(shè)一個(gè)函數(shù)分別為：j(n),k(n),t(n) 則有 i(n)=j(0)+...+j(n-1) j(n)=k(0)+...+k(n-1) k(n)=t(0)+...+t(n-1) i(0)=j(0)=k(0)=0 t(n)=1 而總循環(huán)數(shù)是i(0)+i(1)...+i(n-1) 可以根據(jù)遞推條件得出準(zhǔn)確值 所以算法復(fù)雜度是O(i(0)+i(1)...+i(n-1))

記得采納啊

問(wèn)題七：程序中的時(shí)間復(fù)雜度是怎么計(jì)算的？ 算法復(fù)雜度的介紹，見(jiàn)百科：

baike.baidu/view/7527

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

時(shí)間頻度

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上是不能算出來(lái)的，必須上機(jī)運(yùn)行測(cè)試才能知道。但我們不可能也沒(méi)有必要對(duì)每個(gè)算法都上機(jī)測(cè)試，只需知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。并且一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)時(shí)間就多。一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱(chēng)為語(yǔ)句頻度或時(shí)間頻度。記為T(mén)(n)。

計(jì)算方法

1. 一般情況下，算法的基本操作重復(fù)執(zhí)行的次數(shù)是模塊n的某一個(gè)函數(shù)f（n），因此，算法的時(shí)間復(fù)雜度記做：T（n）=O（f（n））

分析：隨著模塊n的增大，算法執(zhí)行的時(shí)間的增長(zhǎng)率和f（n）的增長(zhǎng)率成正比，所以f（n）越小，算法的時(shí)間復(fù)雜度越低，算法的效率越高。

2. 在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)，再找出T（n）的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n?。?，找出后，f（n）=該數(shù)量級(jí)，若T(n)/f(n)求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T（n）=O（f（n））

例：算法：

for（i=1;i>

問(wèn)題八：人臉識(shí)別的計(jì)算時(shí)間復(fù)雜度怎么算 遞歸算法的時(shí)間復(fù)雜度分析 收藏 在算法分析中，當(dāng)一個(gè)算法中包含遞歸調(diào)用時(shí)，其時(shí)間復(fù)雜度的分析會(huì)轉(zhuǎn)化為一個(gè)遞歸方程求解。實(shí)際上，這個(gè)問(wèn)題是數(shù)學(xué)上求解漸近階的問(wèn)題，而遞歸方程的形式多種多樣，其求解方法也是不一而足，比較常用的有以下四種方法： (1)代入法(Substitution Method) 代入法的基本步驟是先推測(cè)遞歸方程的顯式解，然后用數(shù)學(xué)歸納法來(lái)驗(yàn)證該解是否合理。 (2)迭代法(Iteration Method) 迭代法的基本步驟是迭代地展開(kāi)遞歸方程的右端，使之成為一個(gè)非遞歸的和式，然后通過(guò)對(duì)和式的估計(jì)來(lái)達(dá)到對(duì)方程左端即方程的解的估計(jì)。 (3)套用公式法(Master Method) 這個(gè)方法針對(duì)形如“T(n) = aT(n/b) + f(n)”的遞歸方程。這種遞歸方程是分治法的時(shí)間復(fù)雜性所滿足的遞歸關(guān)系，即一個(gè)規(guī)模為n的問(wèn)題被分成規(guī)模均為n/b的a個(gè)子問(wèn)題，遞歸地求解這a個(gè)子問(wèn)題，然后通過(guò)對(duì)這a個(gè)子間題的解的綜合，得到原問(wèn)題的解。 (4)差分方程法(Difference Formula Method) 可以將某些遞歸方程看成差分方程，通過(guò)解差分方程的方法來(lái)解遞歸方程，然后對(duì)解作出漸近階估計(jì)。 下面就以上方法給出一些例子說(shuō)明。 一、代入法 大整數(shù)乘法計(jì)算時(shí)間的遞歸方程為：T(n) = 4T(n/2) + O(n)，其中T(1) = O(1)，我們猜測(cè)一個(gè)解T(n) = O(n2 )，根據(jù)符號(hào)O的定義，對(duì)n>n0，有T(n) >

問(wèn)題九：如何計(jì)算算法的時(shí)間復(fù)雜度和空間復(fù)雜度 是說(shuō)明一個(gè)程序根據(jù)其數(shù)據(jù)n的規(guī)模大小 所使用的大致時(shí)間和空間

說(shuō)白了 就是表示 如果隨著n的增長(zhǎng) 時(shí)間或空間會(huì)以什么樣的方式進(jìn)行增長(zhǎng)

例

for(int i = 0; i

二、時(shí)間復(fù)雜度怎么算

時(shí)間復(fù)雜度算法記作: T（n）=O（f（n））。

算法的時(shí)間復(fù)雜度，用來(lái)度量算法的運(yùn)行時(shí)間，記作:T（n）=O（f（n））。它表示隨著輸入大小n的增大，算法執(zhí)行需要的時(shí)間的增長(zhǎng)速度可以用f（n）來(lái)描述。因?yàn)閒（n）的增長(zhǎng)速度是大于或者等于T（n）的，即T（n）=O（f（n））。

所以我們可以用f（n）的增長(zhǎng)速度來(lái)度量T（n）的增長(zhǎng)速度，所以我們說(shuō)這個(gè)算法的時(shí)間復(fù)雜度是O(f(n))。如果一個(gè)算法的執(zhí)行次數(shù)是T（n），那么只保留最高次項(xiàng)，同時(shí)忽略最高項(xiàng)的系數(shù)后得到函數(shù)f（n），此時(shí)算法的時(shí)間復(fù)雜度就是O（f（n））。

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

在計(jì)算機(jī)科學(xué)中，時(shí)間復(fù)雜性，又稱(chēng)時(shí)間復(fù)雜度，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定性描述該算法的運(yùn)行時(shí)間。這是一個(gè)代表算法輸入值的字符串的長(zhǎng)度的函數(shù)。時(shí)間復(fù)雜度常用大O符號(hào)表述，不包括這個(gè)函數(shù)的低階項(xiàng)和首項(xiàng)系數(shù)。

使用這種方式時(shí)，時(shí)間復(fù)雜度可被稱(chēng)為是漸近的，亦即考察輸入值大小趨近無(wú)窮時(shí)的情況。為了計(jì)算時(shí)間復(fù)雜度，我們通常會(huì)估計(jì)算法的操作單元數(shù)量，每個(gè)單元運(yùn)行的時(shí)間都是相同的。因此，總運(yùn)行時(shí)間和算法的操作單元數(shù)量最多相差一個(gè)常量系數(shù)。

三、一文講透算法中的時(shí)間復(fù)雜度和空間復(fù)雜度計(jì)算方式

作為一名“程序猿”，大家應(yīng)該都聽(tīng)過(guò)這么一句話：程序=數(shù)據(jù)結(jié)構(gòu)+算法。

這句話是由瑞士計(jì)算機(jī)科學(xué)家尼古拉斯·沃斯（Niklaus Wirth）在 1984 年獲得圖靈獎(jiǎng)時(shí)說(shuō)的一句話，這位大佬還以這句話為名出了一本書(shū)《Algorithms + Data Structures=Programs》，從此這句話就成為了大家耳熟能詳?shù)囊痪涿浴?

隨著時(shí)間的推移，不管這句話是不是非常準(zhǔn)確，但至少能說(shuō)明數(shù)據(jù)結(jié)構(gòu)與算法對(duì)程序來(lái)說(shuō)是非常核心的基礎(chǔ)，如果我們想要寫(xiě)出更多優(yōu)秀優(yōu)雅的代碼，那么數(shù)據(jù)結(jié)構(gòu)與算法是必須要掌握好的。

很多人可能覺(jué)得，我不會(huì)算法，代碼一樣寫(xiě)得很"溜"，算法這東西似乎用處不大?，F(xiàn)在互聯(lián)網(wǎng)的發(fā)達(dá)，我們想要什么幾乎都可以在網(wǎng)上找到現(xiàn)成的，各種框架功能十分強(qiáng)大，似乎看起來(lái)確實(shí)不用算法也可以寫(xiě)出“好代碼”。然而假如我們不懂算法，比如項(xiàng)目中用到了排序，我們?nèi)绾卧u(píng)估代碼的執(zhí)行效率？再比如最常用的 ArrayList 和 LinkedList ，我們?cè)撊绾芜x擇，又比如說(shuō)我們需要去集合中找某一個(gè)數(shù)，又該如何寫(xiě)出性能優(yōu)秀的代碼呢？

同樣的代碼，如何判斷誰(shuí)的代碼是優(yōu)秀的代碼？可讀性，可擴(kuò)展性，健壯性可能都可以用來(lái)判定，然而這些東西我覺(jué)得并不能直接體現(xiàn)出你代碼的優(yōu)秀，因?yàn)閷?duì)用戶而言，訪問(wèn)你的代碼響應(yīng)速度快那就是優(yōu)秀的代碼，相反，動(dòng)輒響應(yīng)幾秒甚至更長(zhǎng)時(shí)間的接口，恐怕就算你可讀性再好，再健壯也稱(chēng)不上是好代碼。

所以說(shuō)一段代碼是否優(yōu)秀，最直接的判斷標(biāo)準(zhǔn)就是性能，而如果要寫(xiě)出高性能的代碼，那么就必須要了解算法，而且拋開(kāi)這個(gè)因素，但凡不想一輩子都寫(xiě) CRUD 代碼的，也需要去了解算法，我們使用的很多框架和中間件底層都有數(shù)據(jù)結(jié)構(gòu)和算法的身影，學(xué)好算法對(duì)我們?cè)创a閱讀時(shí)理解其設(shè)計(jì)思想也是大有裨益的。

要說(shuō)功利性的目的，那就是面試，目前很多大廠的面試，算法基本必面，所以想進(jìn)大廠的話，咱們也得好好學(xué)學(xué)算法。

提到算法，很多人的第一反應(yīng)就是太難學(xué)了，學(xué)不會(huì)，或者說(shuō)經(jīng)常是看完就忘了，但是其實(shí)對(duì)于我們一個(gè)普通的開(kāi)發(fā)者而言，因?yàn)椴⒉恍枰覀內(nèi)グl(fā)明算法，我們需要的僅僅只是去靈活的運(yùn)用算法，所以并不需要非常扎實(shí)的數(shù)據(jù)基礎(chǔ)，當(dāng)然基本的數(shù)學(xué)常識(shí)還是要有的。

如果說(shuō)需要去發(fā)明設(shè)計(jì)一款算法，那就要去推導(dǎo)去證明算法的可行性，這種是需要具有非常扎實(shí)的數(shù)學(xué)基礎(chǔ)的，一般人確實(shí)無(wú)法做到，然而我們普通程序員口中提到算法無(wú)非是二分查找法，哈希算法等，高級(jí)一點(diǎn)的就還有回溯，貪心，動(dòng)態(tài)規(guī)劃等等，這些所謂的算法都是已經(jīng)有現(xiàn)成的公式了，我們要做的無(wú)非就是理解它，然后靈活的運(yùn)用它。這就和我們以前學(xué)習(xí)數(shù)學(xué)公式一樣，給你一個(gè)公式，然后你去做題，做題的過(guò)程其實(shí)就是去靈活地運(yùn)用這個(gè)公式。

算法也是同理，都是有特定方法和特定思路的，我們也并不需要去推導(dǎo)證明這種方式為什么可行，所以學(xué)習(xí)算法沒(méi)有其他訣竅，就是先理解思路，然后多練，等熟練了，自然就可以靈活運(yùn)用了，也不會(huì)說(shuō)學(xué)了立刻就忘了。學(xué)完就忘無(wú)非兩個(gè)原因，一是沒(méi)理解，二是沒(méi)有練習(xí)鞏固。

數(shù)據(jù)結(jié)構(gòu)與算法經(jīng)常是放在一起講，這兩者是沒(méi)辦法獨(dú)立的，因?yàn)樗惴ㄊ菫榱诉_(dá)到某種目的的一種實(shí)現(xiàn)方式，而數(shù)據(jù)結(jié)構(gòu)是一種載體，也就是說(shuō)算法必須依賴數(shù)據(jù)結(jié)構(gòu)這種載體，否則就是空談。換句話說(shuō)：數(shù)據(jù)結(jié)構(gòu)是為算法服務(wù)的，而算法又需要作用在特定的數(shù)據(jù)結(jié)構(gòu)之上。

一個(gè)算法到底好不好，我們?nèi)绾稳ピu(píng)價(jià)？前面我們提到了，你的代碼好不好，最直觀的就是看響應(yīng)速度，算法也一樣，同樣實(shí)現(xiàn)一個(gè)目的（比如說(shuō)排序），誰(shuí)的算法速度快，我們就可以認(rèn)為誰(shuí)的算法更優(yōu)，如果說(shuō)兩種算法實(shí)現(xiàn)的速度差不多，那么我們還可以去評(píng)價(jià)算法所占用的空間，誰(shuí)占用的空間少，那么就可以認(rèn)為誰(shuí)的算法更優(yōu)，這就是算法的基礎(chǔ)：時(shí)間復(fù)雜度和空間復(fù)雜度。

學(xué)習(xí)算法之前，我們必須要學(xué)會(huì)如何分析時(shí)間復(fù)雜度和空間復(fù)雜度（也就是“快”和“省”），否則自己寫(xiě)出來(lái)的算法自己都不知道算法的效率。

接觸過(guò)算法的都知道，算法的時(shí)間復(fù)雜度是用大寫(xiě)的“O”來(lái)表示的，比如： O(1) ， O(n) ， O(logn) ， O(nlogn) ， O(n²) 等等。

變量指的是變量，也就是一段代碼的執(zhí)行時(shí)間是隨著變量的變化而變化的，而不變指的是常量，也就是不論我的變量如何改變，執(zhí)行時(shí)間都不會(huì)改變。

接下來(lái)我們就實(shí)際的來(lái)分析下常用時(shí)間復(fù)雜度的例子來(lái)練習(xí)一下。

0(1) 復(fù)雜度算法也稱(chēng)之為常數(shù)階算法。這里的 1 是用來(lái)代指常量，也就是說(shuō)這個(gè)算法的效率是固定的，無(wú)論你的數(shù)據(jù)量如何變化，效率都一樣，這種復(fù)雜度也是最優(yōu)的一種算法。

上面的示例中不論有多少行代碼，時(shí)間復(fù)雜度都是屬于常數(shù)階段。換言之：只要代碼不存在 循環(huán) ， 遞歸 等循環(huán)類(lèi)調(diào)用，不論代碼有多少行，其復(fù)雜度都是常數(shù)階。

O(n) 復(fù)雜度算法也稱(chēng)之為線性階段。比如下面這個(gè)示例我們應(yīng)該怎么分析復(fù)雜度呢？

前面常量階沒(méi)分析是因?yàn)槌Ａ侩A比較容易理解，接下來(lái)我們就以線性階這個(gè)為例子來(lái)分析下具體是怎么得到的。

我們假設(shè)每一行代碼的執(zhí)行時(shí)間是 T ，那么上面這段代碼的執(zhí)行復(fù)雜度是多少呢？

答案很明顯，那就是 T+n*T ，也就是 (n+1)T ，而在算法中有一個(gè)原則，那就是常量可以被忽略，所以就得到了 nT ，換成大 O 表示法就是 O(n) 。

這只是一個(gè)簡(jiǎn)略的計(jì)算過(guò)程，大家也不用較真說(shuō)每行代碼執(zhí)行時(shí)間可能不一樣之類(lèi)的，也不要較真說(shuō) for 循環(huán)占用了一行，下面的大括號(hào)也占用了一行，如果要較真這個(gè)，那我建議可以去想一下 1=1 為什么等于 2 。

算法中的復(fù)雜度反應(yīng)的只是一個(gè)趨勢(shì)，這里 O(n) 反應(yīng)的就是一個(gè)趨勢(shì)，也就是說(shuō)隨著 n 的變化，算法的執(zhí)行時(shí)間是會(huì)降低的。

知道了上面的線性階，那么平方階就很好理解了，雙層循環(huán)就是平方階，同理，三次循環(huán)就是立方階， k 次循環(huán)就是 k 次方階。

O(logn) 也稱(chēng)之為對(duì)數(shù)階，對(duì)數(shù)階也很常見(jiàn)，像二分查找，二叉樹(shù)之類(lèi)的問(wèn)題中會(huì)見(jiàn)到比較多的對(duì)數(shù)階復(fù)雜度，但是對(duì)數(shù)階也是比較難理解的一種算法復(fù)雜度。

下面我們還是來(lái)看一個(gè)例子：

這段代碼又該如何分析復(fù)雜度呢？這段代碼最關(guān)鍵的就是要分析出 while 循環(huán)中到底循環(huán)了多少次，我們觀察這個(gè)循環(huán)，發(fā)現(xiàn) i 并不是逐一遞增，而是不斷地翻倍： 1->2->4->8->16->32->64 一直到等于 n 為什么才會(huì)結(jié)束，所以我們得到了這樣的一個(gè)公式： 2^x=n 。

也就是說(shuō)我們只要計(jì)算出 x 的值，就得到了循環(huán)次數(shù)，而根據(jù)高中的數(shù)學(xué)知識(shí)我們可以得到 x=log2n （ 2 在下面，是底數(shù)，試了幾種方法都打不出來(lái)，放棄了），所以根據(jù)上面線性階的分析方法，我們省略常量，就得到了示例中的算法復(fù)雜度為 O(log2n) 。

同樣的分析方式，下面的例子，我們可以很快地分析出復(fù)雜度就為 O(log3n) ：

上面得到的 log3n 我們可以再做進(jìn)一步的轉(zhuǎn)換： log3n=log32 * log2n ，而 log32 （注意這幾個(gè)地方的情況 3 是底數(shù)，在下面） 是一個(gè)常量，常量可以省略，所以也就得到了： O(log3n)=O(log2n) 。同樣的道理，不論底數(shù)是多少，其實(shí)最終都可以轉(zhuǎn)化成和 O(log2n) 相等，正因?yàn)槿绱?，為了方便，我們算法中通常就?huì)省略底數(shù)，直接寫(xiě)作 O(logn) 。

上面的數(shù)學(xué)公式大家如果忘了或者看不懂也沒(méi)關(guān)系，只要記住不論對(duì)數(shù)的底數(shù)是多少，我們都算作 O(logn) ，而對(duì)于一個(gè)算法的復(fù)雜度是否是對(duì)數(shù)階，還有一個(gè)簡(jiǎn)易的判斷方法： 當(dāng)循環(huán)中下標(biāo)以指定倍數(shù)形式衰減，那么這就是一個(gè)對(duì)數(shù)階 。

如果理解了上面的對(duì)數(shù)階，那么這種線性對(duì)數(shù)階就非常好理解了，只需要在對(duì)數(shù)階的算法中再嵌一層循環(huán)就是線性對(duì)數(shù)階：

分析了前面這些最常用的時(shí)間復(fù)雜度，其實(shí)我們可以得到以下規(guī)律：

除了上面常用的復(fù)雜度之外，另外還有指數(shù)階，階層階，根號(hào)階等，這些接觸的相對(duì)會(huì)較少，我們就不特意做分析了，如果大家感興趣的話，可以自己去了解下。

前面我們分析的都是只有一段代碼比較復(fù)雜的情況下得到的復(fù)雜度結(jié)果，那么假如我一個(gè)算法中，有多段代碼都比較復(fù)雜呢？這時(shí)候復(fù)雜度該如何分析？

我們先看下面這個(gè)例子：

這個(gè)例子中有三個(gè)循環(huán)，首先第一個(gè)，是一個(gè)常量，那么根據(jù)前面的結(jié)論，不論這個(gè)常量是多大，都屬于常量級(jí)，所以第一個(gè)循環(huán)中的復(fù)雜度為 O(1) ，第二個(gè)和第三個(gè)循環(huán)我們前面也分析過(guò)，復(fù)雜度分別為 O(n) 和 O(n²) 。

也就是這一段代碼中有三段代碼產(chǎn)生了三種不同復(fù)雜度，而且這三個(gè)復(fù)雜度可以很明顯得到的大小關(guān)系為： O(1)<o(n)<o(n²) span=""> </o(n)<o(n²)> ，像這種在同一個(gè)算法中有明確大小關(guān)系的，我們就可以直接取最大值作為這個(gè)算法的復(fù)雜度，所以這個(gè)例子中算法的復(fù)雜度就是 O(n²) 。

接下來(lái)我們?cè)賮?lái)看一個(gè)例子：

這個(gè)例子我們同樣對(duì)三段循環(huán)分別分析可以分別得到如下復(fù)雜度： O(1) ， O(m) ， O(n) 。這時(shí)候我們只能知道 O(1) 最小可以忽略，但是后面兩個(gè)無(wú)法卻無(wú)法確定大小，所以這時(shí)候我們需要取兩段循環(huán)復(fù)雜度之和來(lái)作為算法的復(fù)雜度，所以可以得到這個(gè)例子的算法復(fù)雜度為： O(m+n) 。

上面分析的時(shí)間復(fù)雜度都是比較簡(jiǎn)單的，實(shí)際算法中可能會(huì)比示例中復(fù)雜的多，而且我們示例中只要是循環(huán)都是無(wú)腦循環(huán)，也就是一定從頭循環(huán)到尾，然而實(shí)際中我們有時(shí)候并不需要從頭循環(huán)到尾，可能中途就會(huì)結(jié)束循環(huán)，所以我們根據(jù)實(shí)際情況，又可以將時(shí)間復(fù)雜度從以下四個(gè)方面來(lái)進(jìn)一步分析：

這四種類(lèi)型的時(shí)間復(fù)雜度在這里只會(huì)介紹前面三種，因?yàn)榈谒姆N比較復(fù)雜，而且使用場(chǎng)景也非常有限，而且對(duì)于這四種復(fù)雜度的分析，大家也作為了解就可以，不敢興趣的朋友們可以跳過(guò)這一小部分，因?yàn)樵诮^大部分情況我們只需要分析最壞復(fù)雜度就行，也就是假設(shè)循環(huán)全部執(zhí)行完畢場(chǎng)景下的時(shí)間復(fù)雜度。

我們通過(guò)一個(gè)例子來(lái)理解下最好時(shí)間復(fù)雜度：

這個(gè)方法就是在一個(gè)指定數(shù)組中找到指定元素的下標(biāo)，找不到就返回 -1 ，這個(gè)方法比較簡(jiǎn)單，應(yīng)該比較好理解。

注意這個(gè)方法中的循環(huán)體，如果找到元素，那么就直接返回，這就會(huì)有一個(gè)現(xiàn)象，那就是我這個(gè)循環(huán)體到底會(huì)循環(huán)多少次是不確定的，可能是 1 次，也可能是 n （假設(shè)數(shù)組的長(zhǎng)度） 次，所以假如我們要找的元素就在數(shù)組中的第一個(gè)位置，那么我循環(huán)一次就找到了，這個(gè)算法的復(fù)雜度就是 O(1) ，這就是最好情況時(shí)間復(fù)雜度。

理解了最好時(shí)間復(fù)雜度，那么最壞時(shí)間復(fù)雜度也很好理解了，那就是數(shù)組中不存在我要找到元素，或者說(shuō)最后一個(gè)值才是我要找的元素，那么這樣我就必須循環(huán)完整個(gè)數(shù)組，那么時(shí)間復(fù)雜度就是 O(n) ，這也就是最壞時(shí)間復(fù)雜度。

最好時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度畢竟只有特殊情況才會(huì)發(fā)生，概率還是相對(duì)較小，所以我們很容易就想到我們也需要有一個(gè)平均時(shí)間復(fù)雜度。

我們簡(jiǎn)單的來(lái)分析一下，為了便于分析，我們假設(shè)一個(gè)元素在數(shù)組和不在數(shù)組中的概率都為 1/2 ，然后假如在數(shù)組在，那么又假設(shè)元素出現(xiàn)在每個(gè)位置的概率也是一樣的，也就是每個(gè)位置出現(xiàn)元素的概率為： 1/n 。

所以最終得到的平均時(shí)間復(fù)雜度應(yīng)該等于元素在數(shù)組中和元素不在數(shù)組中兩種情況相加。

因?yàn)樵卦跀?shù)組中的概率為 1/2 ，然后在每個(gè)位置出現(xiàn)的概率也為 1/n 。假如元素出現(xiàn)在第一個(gè)位置，復(fù)雜度為 1*(1/2n) ；假如元素出現(xiàn)在第二個(gè)位置，復(fù)雜度為 2 * (1/2n) ，最終得到當(dāng)前場(chǎng)景下時(shí)間復(fù)雜度為： 1*(1/2n) + 2 * (1/2n) + ... + n*(1/2n) =(n+1)/4。

前面已經(jīng)假定了元素不在數(shù)組中的概率為 1/2 ，所以當(dāng)前場(chǎng)景下的時(shí)間復(fù)雜度為： n * (1/2) ，因?yàn)樵夭辉跀?shù)組中，那么這個(gè)算法必然會(huì)將整個(gè)循環(huán)執(zhí)行完畢，也就循環(huán)是 n 次。

最后我們把兩種情況的復(fù)雜度之和相加就得到了平均時(shí)間復(fù)雜度： (n+1)/4 + n/2 = (3n+1)/4 ，最終我們將常數(shù)類(lèi)的系數(shù)忽略掉，就得到了平均時(shí)間復(fù)雜度為 O(n) 。

均攤時(shí)間復(fù)雜度的算法需要使用攤還分析法，計(jì)算方式相對(duì)有點(diǎn)復(fù)雜，而且使用場(chǎng)景很有限，本文就不做過(guò)多介紹了。

空間復(fù)雜度全稱(chēng)就是漸進(jìn)空間復(fù)雜度，用來(lái)表示算法的存儲(chǔ)空間與數(shù)據(jù)規(guī)模之間的增長(zhǎng)關(guān)系。和時(shí)間復(fù)雜度一樣，空間復(fù)雜度也是用大 O 進(jìn)行表示。

其實(shí)學(xué)會(huì)了分析時(shí)間復(fù)雜度，那么空間復(fù)雜度的分析就簡(jiǎn)單了，主要就看我們?cè)谝粋€(gè)算法當(dāng)中到底有沒(méi)有使用到了額外的空間來(lái)進(jìn)行存儲(chǔ)數(shù)據(jù)，然后判斷這個(gè)額外空間的大小會(huì)不會(huì)隨著 n 的變化而變化，從而得到空間復(fù)雜度。

我們來(lái)看一個(gè)給數(shù)組賦值例子，假設(shè)這就是一個(gè)算法，我們可以來(lái)分析下這個(gè)算法的空間復(fù)雜度：

一開(kāi)始定義了一個(gè)變量，這里需要空間，但是這是一個(gè)常量級(jí)的（不隨 n 的變化而變化），然后再定義了一個(gè)數(shù)組，數(shù)組的長(zhǎng)度為 n ，這里數(shù)組也需要占用空間，而且數(shù)組的空間是隨著 n 的變化而變化的，其余代碼沒(méi)有占用額外空間，所以我們就可以認(rèn)為上面示例中的空間復(fù)雜度為 O(n) 。

對(duì)于算法的空間復(fù)雜度也可以簡(jiǎn)單的進(jìn)行總結(jié)一下：

本文主要講述了為什么要學(xué)習(xí)算法，也簡(jiǎn)單減少了數(shù)據(jù)結(jié)構(gòu)與算法之間的關(guān)系，隨后主要介紹了算法中的入門(mén)知識(shí)：時(shí)間復(fù)雜度和空間復(fù)雜度。想要學(xué)好算法，必須要掌握如何分析一個(gè)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，只有自己會(huì)分析這兩個(gè)個(gè)衡量算法主要性能的標(biāo)準(zhǔn)，才能更好的寫(xiě)出性能優(yōu)秀的算法，同時(shí)我們也講到了最好時(shí)間復(fù)雜度，最壞時(shí)間復(fù)雜度，平均時(shí)間復(fù)雜度和均攤時(shí)間復(fù)雜度，不過(guò)這四種復(fù)雜度的計(jì)算方式大家作為了解即可，等實(shí)際確實(shí)需要使用到再來(lái)回顧也不遲。

四、究竟什么是時(shí)間復(fù)雜度，怎么求時(shí)間復(fù)雜度，看這一篇就夠了

時(shí)間復(fù)雜度就是用來(lái)方便開(kāi)發(fā)者估算出程序的運(yùn)行時(shí)間

我們?cè)撊绾喂烙?jì)程序運(yùn)行時(shí)間呢，我們通常會(huì)估計(jì)算法的操作單元數(shù)量，來(lái)代表程序消耗的時(shí)間， 這里我們默認(rèn)CPU的每個(gè)單元運(yùn)行消耗的時(shí)間都是相同的。

假設(shè)算法的問(wèn)題規(guī)模為n，那么操作單元數(shù)量便用函數(shù)f(n)來(lái)表示

隨著數(shù)據(jù)規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，這稱(chēng)作為算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)時(shí)間復(fù)雜度，記為 O(f(n))

這里就要說(shuō)一下這個(gè)大O，什么是大O呢，很多同學(xué)說(shuō)時(shí)間復(fù)雜度的時(shí)候都知道O(n)，O(n^2)，但說(shuō)不清什么是大O

算法導(dǎo)論給出的解釋?zhuān)?strong> 大O用來(lái)表示上界的 ，當(dāng)用它作為算法的最壞情況運(yùn)行時(shí)間的上界，就是對(duì)任意數(shù)據(jù)輸入的運(yùn)行時(shí)間的上界。

同樣算法導(dǎo)論給出了例子：拿插入排序來(lái)說(shuō)，插入排序的時(shí)間復(fù)雜度我們都說(shuō)是O(n^2)

但是在數(shù)據(jù)本來(lái)有序的情況下時(shí)間復(fù)雜度是O(n)，也就對(duì)于所有輸入情況來(lái)說(shuō)，最壞是O(n^2) 的時(shí)間復(fù)雜度，所以稱(chēng)插入排序的時(shí)間復(fù)雜度為O(n^2)

同樣的同理我們?cè)诳匆幌驴焖倥判颍贾揽焖倥判蚴荗(nlogn)，但是當(dāng)數(shù)據(jù)已經(jīng)有序情況下，快速排序的時(shí)間復(fù)雜度是O(n^2) 的，嚴(yán)格從大O的定義來(lái)講，快速排序的時(shí)間復(fù)雜度應(yīng)該是O(n^2)

但是我們依然說(shuō)快速排序是O(nlogn)的時(shí)間復(fù)雜度，這個(gè)就是業(yè)內(nèi)的一個(gè)默認(rèn)規(guī)定，我們這里說(shuō)的O 代表的就是一般情況，不是嚴(yán)格的上界

所以這里大家知道這么一回事就好了

面試中面試官絕對(duì)不會(huì)針對(duì)快速排序的時(shí)間復(fù)雜度問(wèn)題來(lái)討論O的定義， 大家知道討論的時(shí)間復(fù)雜度就是指一般情況下的時(shí)間復(fù)雜度就好了。

大家要對(duì)算法的時(shí)間復(fù)雜度有這樣的一個(gè)概念

就是同一個(gè)算法的時(shí)間復(fù)雜度不是一成不變的，和輸入的數(shù)據(jù)形式依然有關(guān)系

我們主要關(guān)心的還是一般情況下的數(shù)據(jù)形式 。

面試中說(shuō)道算法的時(shí)間復(fù)雜度是多少指的都是一般情況

但是如果面試官和我們深入探討一個(gè)算法的實(shí)現(xiàn)以及性能的時(shí)候 我們就要時(shí)刻想著 數(shù)據(jù)用例的不一樣 時(shí)間復(fù)雜度也是不同的，這一點(diǎn)同學(xué)們要注意

這個(gè)圖中我們可以看出 不同算法的時(shí)間復(fù)雜度 在不同數(shù)據(jù)輸入規(guī)模下的差異 。

我們?cè)跊Q定使用那些算法的時(shí)候 ，不是時(shí)間復(fù)雜越低的越好，要考慮數(shù)據(jù)規(guī)模，如果數(shù)據(jù)規(guī)模很小 甚至可以用O(n^2)的算法比 O(n)的更合適

就像上圖中圖中 O(5n^2) 和 O(100n) 在n為20之前 很明顯 O(5n^2)是更優(yōu)的，所花費(fèi)的時(shí)間也是最少的。

那我們?yōu)槭裁丛谟?jì)算時(shí)間復(fù)雜度的時(shí)候要忽略常數(shù)項(xiàng)系數(shù)呢，也就說(shuō)O(100n) 就是O(n)的時(shí)間復(fù)雜度，O(5n^2) 就是O(n^2)的時(shí)間復(fù)雜度

而且要默認(rèn)O(n) 優(yōu)于O(n^2) 呢 ？

這里就又涉及到大O的定義

因?yàn)?strong> 大O其實(shí)就是數(shù)據(jù)量級(jí)突破一個(gè)點(diǎn)且數(shù)據(jù)量級(jí)非常大的情況下所表現(xiàn)出的時(shí)間復(fù)雜度 ，這個(gè)點(diǎn)也就是 常數(shù)項(xiàng)系數(shù)已經(jīng)不起決定性作用的點(diǎn)。

例如上圖中 20 就是那個(gè)點(diǎn) ，n只要大于20 常數(shù)項(xiàng)系數(shù)已經(jīng)不起決定性作用了。

所以我們說(shuō)的時(shí)間復(fù)雜度都是省略常數(shù)項(xiàng)系數(shù)的，是因?yàn)橐话闱闆r下我們都是默認(rèn)數(shù)據(jù)規(guī)模足夠的大，基于這樣的事實(shí) 我們給出的算法時(shí)間復(fù)雜的的一個(gè)排行如下所示：

O(1)常數(shù)階 < O(logn)對(duì)數(shù)階 < O(n)線性階 < O(n^2)平方階 < O(n^3)(立方階) < O(2^n) (指數(shù)階)

我們平時(shí)說(shuō)這個(gè) 算法的時(shí)間復(fù)雜度是logn的，一定是log 以2為底n的對(duì)數(shù)么？

其實(shí)不然，也可以是以10為底n的對(duì)數(shù)，也可以是以20為底n的對(duì)數(shù)，但我們統(tǒng)一說(shuō) logn，也就是忽略底數(shù)的描述。

為什么可以這么做呢？

如下圖所示

假如我們有兩個(gè)算法的時(shí)間復(fù)雜度 分別是log以2為底n的對(duì)數(shù) 和 log 以10為底n的對(duì)數(shù)

那么這里如果大家還記得我們高中數(shù)學(xué)的話， 應(yīng)該不能理解 以2為底n的對(duì)數(shù) = 以2為底10的對(duì)數(shù) 乘以 以10為底n的對(duì)數(shù)

那這里以2為底10的對(duì)數(shù) 是一個(gè)常數(shù)，而我在上面已經(jīng)講述了我們計(jì)算時(shí)間復(fù)雜度是忽略常數(shù)項(xiàng)系數(shù)的

抽象一下 log 以i為底n的對(duì)數(shù) 等于 log 以j為底n的對(duì)數(shù)，所以我們忽略了i，直接說(shuō)是logn，正式因?yàn)閘ogij 是就一個(gè)常數(shù)

所以，這樣就應(yīng)該不難理解了 我們?yōu)槭裁春雎缘讛?shù)了

有時(shí)候，我們?nèi)ビ?jì)算時(shí)間復(fù)雜度的時(shí)候 發(fā)現(xiàn)不是一個(gè) 簡(jiǎn)單的O(n) 或者O(n^2)， 而是一個(gè)復(fù)雜的表達(dá)式，例如：

O(2*n^2 + 10*n + 1000)

那這里我們通常如何描述這個(gè)算法的時(shí)間復(fù)雜度呢，一種方法就是簡(jiǎn)化法

去掉運(yùn)行時(shí)間中的加法常數(shù)項(xiàng) （因?yàn)槌?shù)項(xiàng)并不會(huì)因?yàn)閚的增大而增加計(jì)算機(jī)的操作次數(shù)）

O(2*n^2 + 10*n)

去掉常數(shù)系數(shù) （我們剛剛已經(jīng)詳細(xì)講過(guò)為什么可以去掉常數(shù)項(xiàng)的原因了）

O(n^2 + n)

只保留保留最高項(xiàng) 去掉數(shù)量級(jí)小一級(jí)的n （因?yàn)閚^2 的數(shù)據(jù)規(guī)模遠(yuǎn)大于 n），最終簡(jiǎn)化為：

O(n^2)

如果這一步同學(xué)們理解有困難，那也可以做提取n的操作，變成 O(n(n+1)) ，省略加法常數(shù)項(xiàng)后 也別變成了

O(n^2)

所以最后我們說(shuō)：我們這個(gè)算法的算法時(shí)間復(fù)雜度是 O(n^2)

也可以用另一種簡(jiǎn)化的思路，當(dāng)n大于40的時(shí)候 ， 這個(gè)復(fù)雜度 會(huì)一直小于 O(3*n^2)

O(2*n^2 + 10*n + 1000) < O(3*n^2)

所以說(shuō) 最后我們省略掉常數(shù)項(xiàng)系數(shù)最終時(shí)間復(fù)雜度也是 O(n^2)

我們通過(guò)一道題目，來(lái)看一下具體時(shí)間復(fù)雜度應(yīng)該怎么算

題目描述：找出n個(gè)字符串中相同的兩個(gè)字符串（假設(shè)這里只有兩個(gè)相同的字符串）

一些同學(xué)可能以為解決這道題目可以采用枚舉遍歷的解法，時(shí)間復(fù)雜度是 O(n^2)

這個(gè)時(shí)間復(fù)雜度其實(shí)是不對(duì)的。

這里 一些同學(xué)忽略了字符串比較的時(shí)間消耗，這里并不像int 型數(shù)字做比較那么簡(jiǎn)單

除了n^2 次的遍歷次數(shù)外， 字符串比較依然要消耗m次操作（m也就是字母串的長(zhǎng)度），所以時(shí)間復(fù)雜度是 O(m*n*n)

那么我們?cè)傧胍幌缕渌忸}思路

我們先排對(duì)n個(gè)字符串按字典序來(lái)排序，排序后n個(gè)字符串就是有序的，意味著兩個(gè)相同的字符串就是挨在一起

然后在遍歷一遍n個(gè)字符串，這樣就找到兩個(gè)相同的字符串了

那我們來(lái)看看這種算法的時(shí)間復(fù)雜度

快速排序時(shí)間復(fù)雜度 為O(nlogn)，依然要考慮字符串的長(zhǎng)度是m，那么快速排序每次的比較都要有m次的字符比較的操作，就是 O(m*n*logn)

之后我們還要遍歷一遍這n個(gè)字符串找出兩個(gè)相同的字符串，別忘了遍歷的時(shí)候依然要比較字符串，所以總共的時(shí)間復(fù)雜度是 O(m*n*logn + n*m)

我們對(duì) O(m*n*logn + n*m) 進(jìn)行簡(jiǎn)化操作，把 m*n 提取出來(lái)變成 O(m*n*(logn + 1)) ，

在省略常數(shù)項(xiàng)最后的時(shí)間復(fù)雜度是 O(m*n*logn) ， 那我們比較一下時(shí)間效率 O(m*n*logn) 是不是比第一種方法 O(m*n*n) 更快一些呢

很明顯 O(m*n*logn) 要優(yōu)于 O(m*n*n)

所以 先把字符串集合排序在遍歷一遍找到兩個(gè)相同字符串的方式要比直接暴力枚舉的方式更快 。

通過(guò)這個(gè)例子 希望大家對(duì)時(shí)間復(fù)雜的是怎么算的有一個(gè)初步的理解和認(rèn)識(shí)。

以上就是關(guān)于計(jì)算復(fù)雜度和時(shí)間復(fù)雜度相關(guān)問(wèn)題的回答。希望能幫到你，如有更多相關(guān)問(wèn)題，您也可以聯(lián)系我們的客服進(jìn)行咨詢，客服也會(huì)為您講解更多精彩的知識(shí)和內(nèi)容。

推薦閱讀：

杭州計(jì)算機(jī)工資怎么樣（杭州計(jì)算機(jī)工資怎么樣知乎）

給水水力計(jì)算圖（給水工程水力計(jì)算表）

指數(shù)在計(jì)算器上怎么按

英文版狗屁文章生成器

東莞長(zhǎng)安百立英語(yǔ)招聘（東莞長(zhǎng)安百力廠好不好）