求關(guān)注

帶你了解時(shí)間復(fù)雜度和空間復(fù)雜度到底是什么？

1. 前言

算法（Algorithm）是指用來(lái)操作數(shù)據(jù)验毡、解決程序問題的一組方法衡创。對(duì)于同一個(gè)問題，使用不同的算法晶通，也許最終得到的結(jié)果是一樣的璃氢，但在過程中消耗的資源和時(shí)間卻會(huì)有很大的區(qū)別。那么我們應(yīng)該如何去衡量不同算法之間的優(yōu)劣呢狮辽？

主要還是從算法所占用的「時(shí)間」和「空間」兩個(gè)維度去考量一也。

• 時(shí)間維度：是指執(zhí)行當(dāng)前算法所消耗的時(shí)間，我們通常用「時(shí)間復(fù)雜度」來(lái)描述喉脖。

• 空間維度：是指執(zhí)行當(dāng)前算法需要占用多少內(nèi)存空間椰苟，我們通常用「空間復(fù)雜度」來(lái)描述。

因此树叽，評(píng)價(jià)一個(gè)算法的效率主要是看它的時(shí)間復(fù)雜度和空間復(fù)雜度情況舆蝴。然而，有的時(shí)候時(shí)間和空間卻又是「魚和熊掌」题诵，不可兼得的洁仗，那么我們就需要從中去取一個(gè)平衡點(diǎn)。

2. 算法的介紹

排序也稱排序算法(Sort Algorithm)性锭，排序是將一組數(shù)據(jù)赠潦，依指定的順序進(jìn)行排列的過程。

3. 排序的分類

3.1 內(nèi)部排序

指將需要處理的所有數(shù)據(jù)都加載到內(nèi)部存儲(chǔ)器 (內(nèi)存)中進(jìn)行排序草冈。

3.2 外部排序法

數(shù)據(jù)量過大祭椰，無(wú)法全部加載到內(nèi)存中臭家，需要借助外部存儲(chǔ)(文件等)進(jìn)行排序。

3.3 常見的排序算法分類(見下圖)

排序

4. 算法的時(shí)間復(fù)雜度

4.1 度量程序(算法)執(zhí)行時(shí)間方法

4.1.1 事后統(tǒng)計(jì)的方法

這種方法可行, 但是有兩個(gè)問題：一是要想對(duì)設(shè)計(jì)的算法的運(yùn)行性能進(jìn)行評(píng)測(cè)方淤，需要實(shí)際運(yùn)行該程序钉赁；二是所得時(shí)間的統(tǒng)計(jì)量依賴于計(jì)算機(jī)的硬件、軟件等環(huán)境因素, 這種方式携茂，要在同一臺(tái)計(jì)算機(jī)的相同狀態(tài)下運(yùn)行你踩，才能比較哪個(gè)算法速度更快。

4.1.2 事前估算的方法

因事后統(tǒng)計(jì)方法更多的依賴于計(jì)算機(jī)的硬件讳苦、軟件等環(huán)境因素带膜，有時(shí)容易掩蓋算法本身的優(yōu)劣。因此人們常常采用事前分析估算的方法鸳谜。
在編寫程序前膝藕，依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。一個(gè)用高級(jí)語(yǔ)言編寫的程序在計(jì)算機(jī)上運(yùn)行時(shí)所消耗的時(shí)間取決于下列因素：
(1) 算法采用的策略咐扭、方法
(2) 編譯產(chǎn)生的代碼質(zhì)量
(3) 問題的輸入規(guī)模
(4) 機(jī)器執(zhí)行指令的速度芭挽。

通過分析某個(gè)算法的時(shí)間復(fù)雜度來(lái)判斷哪個(gè)算法更優(yōu)。

4.2 時(shí)間頻度

4.2.1 基本介紹

時(shí)間頻度：一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例蝗肪，哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多袜爪，它花費(fèi)時(shí)間就多。 一個(gè)算法中的語(yǔ)句執(zhí)行次數(shù)稱為語(yǔ)句頻度或時(shí)間頻度薛闪。記為 T(n)辛馆。

舉例說(shuō)明-基本案例

比如計(jì)算 1-1000 所有數(shù)字之和, 我們?cè)O(shè)計(jì)兩種算法：

舉例說(shuō)明-基本案例

舉例說(shuō)明-忽略常數(shù)項(xiàng)

舉例說(shuō)明-忽略常數(shù)項(xiàng)

1. 2n+20 和 2n 隨著 n 變大，執(zhí)行曲線無(wú)限接近, 20 可以忽略
2. 3n+10 和 3n 隨著 n 變大豁延，執(zhí)行曲線無(wú)限接近, 10 可以忽略

舉例說(shuō)明-忽略低次項(xiàng)

舉例說(shuō)明-忽略低次項(xiàng)

舉例說(shuō)明-忽略低次項(xiàng)

結(jié)論:

1. 2n^2+3n+10 和 2n^2 隨著 n 變大, 執(zhí)行曲線無(wú)限接近, 可以忽略 3n+10
2. n^2+5n+20 和 n^2 隨著 n 變大,執(zhí)行曲線無(wú)限接近, 可以忽略 5n+20

舉例說(shuō)明-忽略系數(shù)

舉例說(shuō)明-忽略系數(shù)

舉例說(shuō)明-忽略系數(shù)

結(jié)論:

1. 隨著 n 值變大昙篙，5n^2+7n 和 3n^2 + 2n ，執(zhí)行曲線重合, 說(shuō)明 這種情況下, 5 和 3 可以忽略诱咏。
2. 而 n^3+5n 和 6n^3+4n 苔可，執(zhí)行曲線分離，說(shuō)明多少次方式關(guān)鍵

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

1. 一般情況下胰苏，算法中的基本操作語(yǔ)句的重復(fù)執(zhí)行次數(shù)是問題規(guī)模 n 的某個(gè)函數(shù)硕蛹，用 T(n)表示，若有某個(gè)輔助函數(shù) f(n)硕并，使得當(dāng) n 趨近于無(wú)窮大時(shí)法焰，T(n) / f(n) 的極限值為不等于零的常數(shù)，則稱 f(n)是 T(n)的同數(shù)量級(jí)函數(shù)倔毙。記作 T(n)= Ｏ( f(n) )埃仪，稱Ｏ( f(n) ) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度陕赃。
2. T(n) 不同卵蛉，但時(shí)間復(fù)雜度可能相同颁股。 如：T(n)=n2+7n+6 與 T(n)=3n2+2n+2 它們的 T(n) 不同，但時(shí)間復(fù)雜度相同傻丝，都為 O(n2)甘有。
3. 計(jì)算時(shí)間復(fù)雜度的方法：

• 用常數(shù) 1 代替運(yùn)行時(shí)間中的所有加法常數(shù) T(n)=n2+7n+6 => T(n)=n2+7n+1
• 修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng) T(n)=n2+7n+1 => T(n) = n2
• 去除最高階項(xiàng)的系數(shù) T(n) = n2 => T(n) = n2 => O(n2)

4.4 常見的時(shí)間復(fù)雜度

1. 常數(shù)階 O(1)
2. 對(duì)數(shù)階 O(log2n)
3. 線性階 O(n)
4. 線性對(duì)數(shù)階 O(nlog2n)
5. 平方階 O(n^2)
6. 立方階 O(n^3)
7. k 次方階 O(n^k)
8. 指數(shù)階 O(2^n)

4.4.1 常見的時(shí)間復(fù)雜度對(duì)應(yīng)的圖

常見的時(shí)間復(fù)雜度對(duì)應(yīng)的圖

1. 常見的算法時(shí)間復(fù)雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(nk)＜Ο(2n) 葡缰，隨著問題規(guī)模 n 的不斷增大亏掀，上述時(shí)間復(fù)雜度不斷增大，算法的執(zhí)行效率越低
2. 從圖中可見泛释，我們應(yīng)該盡可能避免使用指數(shù)階的算法

4.4.1.1 常數(shù)階 O(1)

無(wú)論代碼執(zhí)行了多少行滤愕，只要是沒有循環(huán)等復(fù)雜結(jié)構(gòu)，那這個(gè)代碼的時(shí)間復(fù)雜度就都是O(1)怜校。

常數(shù)階

上述代碼在執(zhí)行的時(shí)候间影，它消耗的時(shí)候并不隨著某個(gè)變量的增長(zhǎng)而增長(zhǎng)，那么無(wú)論這類代碼有多長(zhǎng)茄茁，即使有幾萬(wàn)幾十萬(wàn)行魂贬，都可以用O(1)來(lái)表示它的時(shí)間復(fù)雜度。

4.4.1.2 對(duì)數(shù)階 O(log2n)

對(duì)數(shù)階

說(shuō)明： 在while循環(huán)里面胰丁，每次都將 i 乘以 2随橘，乘完之后喂分，i 距離 n 就越來(lái)越近了锦庸。假設(shè)循環(huán)x次之后，i 就大于 n 了蒲祈，此時(shí)這個(gè)循環(huán)就退出了甘萧，也就是說(shuō) 2 的 x 次方等于 n，那么 x = log2n也就是說(shuō)當(dāng)循環(huán) log2n 次以后梆掸，這個(gè)代碼就結(jié)束了扬卷。因此這個(gè)代碼的時(shí)間復(fù)雜度為：O(log2n) 。 O(log2n) 的這個(gè)2 時(shí)間上是根據(jù)代碼變化的酸钦，i = i * 3 怪得，則是 O(log3n) 。

對(duì)數(shù)

4.4.1.3 線性階 O(n)

線性階

4.4.1.4 線性對(duì)數(shù)階 O(nlogN)

線性對(duì)數(shù)階

4.4.1.5 平方階 O(n2)

平方階

4.4.1.6 立方階 O(n3)魔眨、K 次方階 O(n^k)

說(shuō)明： 參考上面的 O(n2) 去理解就好了，O(n3)相當(dāng)于三層 n 循環(huán)酿雪，其它的類似

4.5 平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度

1. 平均時(shí)間復(fù)雜度是指所有可能的輸入實(shí)例均以等概率出現(xiàn)的情況下遏暴，該算法的運(yùn)行時(shí)間。

2. 最壞情況下的時(shí)間復(fù)雜度稱最壞時(shí)間復(fù)雜度指黎。 一般討論的時(shí)間復(fù)雜度均是最壞情況下的時(shí)間復(fù)雜度朋凉。這樣做的原因是：最壞情況下的時(shí)間復(fù)雜度是算法在任何輸入實(shí)例上運(yùn)行時(shí)間的界限，這就保證了算法的運(yùn)行時(shí)間不會(huì)比最壞情況更長(zhǎng)醋安。

3. 平均時(shí)間復(fù)雜度和最壞時(shí)間復(fù)雜度是否一致杂彭，和算法有關(guān)(如下圖)。

排序算法時(shí)間復(fù)雜度與空間復(fù)雜度

4. 空間復(fù)雜度

4.1 簡(jiǎn)介

1. 類似于時(shí)間復(fù)雜度的討論吓揪，一個(gè)算法的空間復(fù)雜度(Space Complexity)定義為該算法所耗費(fèi)的存儲(chǔ)空間亲怠，它也是問題規(guī)模 n 的函數(shù)。
2. 空間復(fù)雜度(Space Complexity)是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度柠辞。有的算法需要占用的臨時(shí)工作單元數(shù)與解決問題的規(guī)模 n 有關(guān)团秽，它隨著 n 的增大而增大，當(dāng) n 較大時(shí)叭首，將占用較多的存儲(chǔ)單元习勤，例如快速排序和歸并排序算法, 基數(shù)排序就屬于這種情況
3. 在做算法分析時(shí)，主要討論的是時(shí)間復(fù)雜度焙格。 從用戶使用體驗(yàn)上看图毕，更看重的程序執(zhí)行的速度。一些緩存產(chǎn)品(redis, memcache)和算法(基數(shù)排序)本質(zhì)就是用空間換時(shí)間眷唉。

4.2 定義

算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)予颤，算法的空間復(fù)雜度的計(jì)算公式記作：S(n)=O(f(n))，其中冬阳，n為問題的規(guī)模蛤虐，f(n)為語(yǔ)句關(guān)于n所占存儲(chǔ)空間的函數(shù)。

4.3 舉例說(shuō)明

例如：如何判斷某年是不是閏年摩泪？

方法一

寫一個(gè)算法笆焰，每給一個(gè)年份，就可以通過該算法計(jì)算得到是否閏年的結(jié)果见坑。

方法二

先建立一個(gè)所有年份的數(shù)組嚷掠，然后把所有的年份按下標(biāo)的數(shù)字對(duì)應(yīng)捏检，如果是閏年，則此數(shù)組元素的值是1不皆，如果不是元素的值則為0贯城。這樣，所謂的判斷某一年是否為閏年就變成了查找這個(gè)數(shù)組某一個(gè)元素的值的問題霹娄。

第一種方法相比起第二種來(lái)說(shuō)很明顯非常節(jié)省空間能犯，但每一次查詢都需要經(jīng)過一系列的計(jì)算才能知道是否為閏年。
第二種方法雖然需要在內(nèi)存里存儲(chǔ)所有年份的數(shù)組犬耻，但是每次查詢只需要一次索引判斷即可踩晶。

這是空間和時(shí)間互換的例子。到底哪一種方法好枕磁？其實(shí)還是要看具體用在什么地方渡蜻。

文末

歡迎關(guān)注個(gè)人微信公眾號(hào)：Coder編程
獲取最新原創(chuàng)技術(shù)文章和免費(fèi)學(xué)習(xí)資料，更有大量精品思維導(dǎo)圖计济、面試資料茸苇、PMP備考資料等你來(lái)領(lǐng)，方便你隨時(shí)隨地學(xué)習(xí)技術(shù)知識(shí)沦寂！

微信公眾號(hào)

求關(guān)注