如何掌握時間復(fù)雜度與空間復(fù)雜度

這篇文章主要講解了“如何掌握時間復(fù)雜度與空間復(fù)雜度”，文中的講解內(nèi)容簡單清晰，易于學(xué)習(xí)與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學(xué)習(xí)“如何掌握時間復(fù)雜度與空間復(fù)雜度”吧！

前言

算法(Algorithm)是指用來操作數(shù)據(jù)、解決程序問題的一組方法。算法是大廠、外企面試的必備項，也是每個高級程序員的必備技能。針對同一問題，可以有很多種算法來解決，但不同的算法在效率和占用存儲空間上的區(qū)別可能會很大。

那么，通過什么指標(biāo)來衡量算法的優(yōu)劣呢?其中，上面提到的效率可以用算法的時間復(fù)雜度來描述，而所占用的存儲空間可以用算法的空間復(fù)雜度來描述。

• 時間復(fù)雜度：用于評估執(zhí)行程序所消耗的時間，可以估算出程序?qū)μ幚砥鞯氖褂贸潭取?/p>

• 空間復(fù)雜度：用于評估執(zhí)行程序所占用的內(nèi)存空間，可以估算出程序?qū)τ嬎銠C(jī)內(nèi)存的使用程度。

在實踐中或面試中，我們不僅要能夠?qū)懗鼍唧w的算法來，還要了解算法的時間復(fù)雜度和空間復(fù)雜度，這樣才能夠評估出算法的優(yōu)劣。當(dāng)時間復(fù)雜度和空間復(fù)雜度無法同時滿足時，還需要從中選取一個平衡點。

一個算法通常存在最好、平均、最壞三種情況，我們一般關(guān)注的是最壞情況。最壞情況是算法運行時間的上界，對于某些算法來說，最壞情況出現(xiàn)的比較頻繁，也意味著平均情況和最壞情況一樣差。

通常，時間復(fù)雜度要比空間復(fù)雜度更容易出問題，更多研究的是時間復(fù)雜度，面試中如果沒有特殊說明，講的也是時間復(fù)雜度。

時間復(fù)雜度

要獲得算法的時間復(fù)雜度，最直觀的想法是把算法程序運行一遍，自然可以獲得。但實踐中往往受限于測試環(huán)境、數(shù)據(jù)規(guī)模等因素，直接測試算法要么難以實現(xiàn)，要么誤差較大，而且理論上也沒必要對每個算法都進(jìn)行一遍測試，只需要找到一種評估指標(biāo)，獲得算法執(zhí)行所消耗時間的基本趨勢即可。

時間頻度

通常，一個算法所花費的時間與代碼語句執(zhí)行的次數(shù)成正比，算法執(zhí)行語句越多，消耗的時間也就越多。我們把一個算法中的語句執(zhí)行次數(shù)稱為時間頻度，記作T(n)。

漸進(jìn)時間復(fù)雜度

在時間頻度T(n)中，n代表著問題的規(guī)模，當(dāng)n不斷變化時，T(n)也會不斷地隨之變化。那么，如果我們想知道T(n)隨著n變化時會呈現(xiàn)出什么樣的規(guī)律，那么就需要引入時間復(fù)雜度的概念。

一般情況下，算法基本操作的重復(fù)執(zhí)行次數(shù)為問題規(guī)模n的某個函數(shù)，也就是用時間頻度T(n)表示。如果存在某個函數(shù)f(n)，使得當(dāng)n趨于無窮大時，T(n)/f(n)的極限值是不為零的常數(shù)，那么f(n)是T(n)的同數(shù)量級函數(shù)，記作T(n)=O(f(n))，稱O(f(n))為算法的漸進(jìn)時間復(fù)雜度，簡稱為時間復(fù)雜度。

漸進(jìn)時間復(fù)雜度用大寫O表示，所以也稱作大O表示法。算法的時間復(fù)雜度函數(shù)為：T(n)=O(f(n));

T(n)=O(f(n))表示存在一個常數(shù)C，使得在當(dāng)n趨于正無窮時總有 T(n) ≤ C *  f(n)。簡單來說，就是T(n)在n趨于正無窮時最大也就跟f(n)差不多大。也就是說當(dāng)n趨于正無窮時T(n)的上界是C *  f(n)。其雖然對f(n)沒有規(guī)定，但是一般都是取盡可能簡單的函數(shù)。

常見的時間復(fù)雜度有：O(1)常數(shù)型;O(log n)對數(shù)型，O(n)線性型，O(nlog  n)線性對數(shù)型，O(n2)平方型，O(n3)立方型，O(nk)k次方型，O(2n)指數(shù)型。

上圖為不同類型的函數(shù)的增長趨勢圖，隨著問題規(guī)模n的不斷增大，上述時間復(fù)雜度不斷增大，算法的執(zhí)行效率越低。

常見的算法時間復(fù)雜度由小到大依次為：&Omicron;(1)<&Omicron;(log n)<&Omicron;(n)<&Omicron;(nlog  n)<&Omicron;(n2)<&Omicron;(n3)<&hellip;<&Omicron;(2^n)<&Omicron;(n!)。

值得留意的是，算法復(fù)雜度只是描述算法的增長趨勢，并不能說一個算法一定比另外一個算法高效。這要添加上問題規(guī)模n的范圍，在一定問題規(guī)范范圍之前某一算法比另外一算法高效，而過了一個閾值之后，情況可能就相反了，通過上圖我們可以明顯看到這一點。這也就是為什么我們在實踐的過程中得出的結(jié)論可能上面算法的排序相反的原因。

如何推導(dǎo)時間復(fù)雜度

上面我們了解了時間復(fù)雜度的基本概念及表達(dá)式，那么實踐中我們怎么樣才能通過代碼獲得對應(yīng)的表達(dá)式呢?這就涉及到求解算法復(fù)雜度。

求解算法復(fù)雜度一般分以下幾個步驟：

• 找出算法中的基本語句：算法中執(zhí)行次數(shù)最多的語句就是基本語句，通常是最內(nèi)層循環(huán)的循環(huán)體。

• 計算基本語句的執(zhí)行次數(shù)的數(shù)量級：只需計算基本語句執(zhí)行次數(shù)的數(shù)量級，即只要保證函數(shù)中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數(shù)。這樣能夠簡化算法分析，使注意力集中在最重要的一點上：增長率。

• 用大&Omicron;表示算法的時間性能：將基本語句執(zhí)行次數(shù)的數(shù)量級放入大&Omicron;記號中。

其中用大O表示法通常有三種規(guī)則：

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

• 只保留時間函數(shù)中的最高階項;

• 如果最高階項存在，則省去最高階項前面的系數(shù);

下面通過具體的實例來說明以上的推斷步驟和規(guī)則。

時間復(fù)雜度實例

常數(shù)階O(1)

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

int i = 1; int j = 2; int k = 1 + 2;

上述代碼執(zhí)行時，單個語句的頻度均為1，不會隨著問題規(guī)模n的變化而變化。因此，算法時間復(fù)雜度為常數(shù)階，記作T(n)=O(1)。這里我們需要注意的是，即便上述代碼有成千上萬行，只要執(zhí)行算法的時間不會隨著問題規(guī)模n的增長而增長，那么執(zhí)行時間只不過是一個比較大的常數(shù)而已。此類算法的時間復(fù)雜度均為O(1)。

對數(shù)階O(log n)

先來看對應(yīng)的示例代碼：

int i = 1; // ① while (i <= n) {    i = i * 2; // ② }

在上述代碼中，語句①的頻度為1，可以忽略不計。

語句②我們可以看到它是以2的倍數(shù)來逼近n，每次都乘以2。如果用公式表示就是122*2&hellip;*2  <=n，也就是說2的x次方小于等于n時會執(zhí)行循環(huán)體，記作2^x <=  n，于是得出x<=logn。也就是說上述循環(huán)在執(zhí)行l(wèi)ogn次之后，便結(jié)束了，因此上述代碼的時間復(fù)雜度為O(log n)。

其實上面代碼的時間復(fù)雜度公式如果精確的來講應(yīng)該是：T(n) = 1 + O(log  n)，但我們上面已經(jīng)講到對應(yīng)的原則，“只保留時間函數(shù)中的最高階項”，因此記作O(log n)。

線性階O(n)

示例代碼：

int j = 0; // ① for (int i = 0; i < n; i++) { // ②    j = i; // ③    j++; // ④ }

上述代碼中，語句①的頻度為1，②的頻度為n，③的頻度為n-1，④的頻度為n-1，因此整個算法可以用公式T(n)=1+n+(n-1)+(n-1)來表示。進(jìn)而可以推到T(n)=1+n+(n-1)+(n-1)=3n-1，即O(n)=3n-1，去掉低次冪和系數(shù)即O(n)=n，因此T(n)=O(n)。

在上述代碼中for循環(huán)中的代碼會執(zhí)行n遍，因此它消耗的時間是隨著n的變化而成線性變化的，因此這類算法都可以用O(n)來表示時間復(fù)雜度。

線性對數(shù)階O(nlogN)

示例代碼：

for (int m = 1; m < n; m++) {    int i = 1; // ①    while (i <= n) {       i = i * 2; // ②    } }

線性對數(shù)階要對照對數(shù)階 O(log  n)來進(jìn)行理解。上述代碼中for循環(huán)內(nèi)部的代碼便是上面講到對數(shù)階，只不過在對數(shù)階的外面套了一個n次的循環(huán)，當(dāng)然，它的時間復(fù)雜度就是n*O(log  n)了，于是記作O(nlog n)。

平方階O(n&sup2;)

示例代碼：

int k = 0; for (int i = 0; i < n; i++) {    for (int j = 0; j < n; j++) {       k++;    } }

平方階可對照線性階來進(jìn)行理解，我們知道線性階是一層for循環(huán)，記作O(n)，此時等于又嵌套了一層for循環(huán)，那么便是n * O(n)，也就是O(n *  n)，即O(n^2)。

如果將外層循環(huán)中的n改為m，即：

int k = 0; for (int i = 0; i < m; i++) {    for (int j = 0; j < n; j++) {       k++;    } }

那么，對應(yīng)的時間復(fù)雜度便為：O(m * n)。

同理，立方階O(n&sup3;)、K次方階O(n^k)，只不過是嵌套了3層循環(huán)、k層循環(huán)而已。

排序算法對比

上面介紹了各種示例算法的時間復(fù)雜度推理過程，對照上面的時間復(fù)雜度以及算法效率的大小，來看一下我們常見的針對排序的幾種算法的時間復(fù)雜度對比。

空間復(fù)雜度

最后，我們再了解一下空間復(fù)雜度。空間復(fù)雜度主要指執(zhí)行算法所需內(nèi)存的大小，用于對程序運行過程中所需要的臨時存儲空間的度量，這里的空間復(fù)雜度同樣是預(yù)估的。

程序執(zhí)行除了需要存儲空間、指令、常數(shù)、變量和輸入數(shù)據(jù)外，還包括對數(shù)據(jù)進(jìn)行操作的工作單元和存儲計算所需信息的輔助空間。存儲空間通常包括：指令空間(即代碼空間)、數(shù)據(jù)空間(常量、簡單變量)等所占的固定部分和動態(tài)分配、遞歸棧所需的可變空間。其中可變空間與算法有關(guān)。

一個算法所需的存儲空間用f(n)表示。S(n)=O(f(n))其中n為問題的規(guī)模，S(n)表示空間復(fù)雜度。

下面看兩個常見的空間復(fù)雜度示例：空間復(fù)雜度O(1)和O(n)。

空間復(fù)雜度 O(1)

空間復(fù)雜度為O(1)的情況的示例代碼與時間復(fù)雜度為O(1)的實例代碼一致：

int i = 1; int j = 2; int k = 1 + 2;

上述代碼中臨時空間并不會隨著n的變化而變化，因此空間復(fù)雜度為O(1)。總結(jié)一下就是：如果算法執(zhí)行所需要的臨時空間不隨著某個變量n的大小而變化，此算法空間復(fù)雜度為一個常量，可表示為  O(1)，即 S(n) = O(1)。

空間復(fù)雜度 O(n)

示例代碼：

int j = 0; int[] m = new int[n]; for (int i = 1; i <= n; ++i) {    j = i;    j++; }

上述代碼中，只有創(chuàng)建int數(shù)組分配空間時與n的大小有關(guān)，而for循環(huán)內(nèi)沒有再分配新的空間，因此，對應(yīng)的空間復(fù)雜度為S(n) = O(n)。

感謝各位的閱讀，以上就是“如何掌握時間復(fù)雜度與空間復(fù)雜度”的內(nèi)容了，經(jīng)過本文的學(xué)習(xí)后，相信大家對如何掌握時間復(fù)雜度與空間復(fù)雜度這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關(guān)知識點的文章，歡迎關(guān)注！