前言

在參加面試的時(shí)候，多多少少都會(huì)問(wèn)到一些關(guān)于算法的知識(shí)。

這其實(shí)是有原因的：在多個(gè)人專(zhuān)業(yè)知識(shí)相同的情況下，公司為什么選擇放棄他人而選擇你，其中的一個(gè)因素就是看你的算法基礎(chǔ)。

本文將詳細(xì)介紹算法的基礎(chǔ)概念，如果對(duì)算法不太理解的同學(xué)可以借鑒參考。

算法基礎(chǔ)

一、概念

根據(jù)《算法導(dǎo)論第三版》中的描述：算法就是任何問(wèn)題的解決過(guò)程，它接收一些值或集合，對(duì)這些值或集合進(jìn)行加工，最后產(chǎn)生一些值或集合作為輸出，算法指的就是將輸入轉(zhuǎn)換為輸出這個(gè)過(guò)程中的一系列計(jì)算流程。

簡(jiǎn)而言之，我們可以說(shuō)算法就是解決一個(gè)特定任務(wù)的一系列步驟。

二、特征

一個(gè)算法應(yīng)具有以下五個(gè)重要特征：

• 有窮性：算法必須在執(zhí)行有限個(gè)步驟后終止，如果你設(shè)計(jì)的算法永無(wú)休止地嘗試解決問(wèn)題，那么它是無(wú)用的；
• 確切性：算法的每一步指令都必須具有確切的意義，并且在任何場(chǎng)景下，每一步指令都應(yīng)該沒(méi)有歧義；
• 有效性(可行性)：一個(gè)算法設(shè)計(jì)出來(lái)是用以解決某個(gè)問(wèn)題的，如果你設(shè)計(jì)的算法不能解決問(wèn)題，那么它也是無(wú)用的；
• 輸入項(xiàng)：一個(gè)算法有0個(gè)或者多個(gè)輸入，用來(lái)初始化算法，這主要看你設(shè)計(jì)的算法需不需要輸入?yún)?shù)；
• 輸出項(xiàng)：一個(gè)算法有1個(gè)或者多個(gè)輸出。沒(méi)有輸出項(xiàng)的算法是毫無(wú)意義的，輸出項(xiàng)反映了數(shù)據(jù)加工后的結(jié)果。

三、評(píng)定

針對(duì)同一個(gè)問(wèn)題，可以用多種算法來(lái)解決，不過(guò)具體用哪個(gè)就由每個(gè)算法的效率來(lái)決定了。一個(gè)算法的質(zhì)量?jī)?yōu)劣將會(huì)影響程序的執(zhí)行效率。

那么如何分析一個(gè)算法的優(yōu)劣呢？主要是從時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)考慮：

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

指執(zhí)行算法所需要的計(jì)算工作量，簡(jiǎn)單點(diǎn)說(shuō)就是指執(zhí)行算法所需要消耗的時(shí)間。

一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上來(lái)講是不能算出來(lái)的，必須通過(guò)計(jì)算機(jī)運(yùn)行測(cè)試才能知道。

不過(guò)一個(gè)算法具體耗費(fèi)多少時(shí)間我們并不關(guān)心，我們只需要知道哪個(gè)算法花費(fèi)的時(shí)間多，哪個(gè)算法花費(fèi)的時(shí)間少就可以了。

一個(gè)算法花費(fèi)的時(shí)間與算法中語(yǔ)句的執(zhí)行次數(shù)成正比例。哪個(gè)算法中語(yǔ)句執(zhí)行次數(shù)多，它花費(fèi)的時(shí)間就多。

此時(shí)我們引入時(shí)間頻度的概念，記為T(mén)(n)。

n指的是問(wèn)題的規(guī)模，當(dāng)n不斷變化時(shí)，時(shí)間頻度T(n)也會(huì)不斷變化。

我們想要呈現(xiàn)出它的變化規(guī)律，為此，我們引入了時(shí)間復(fù)雜度的概念。

一般來(lái)說(shuō)，假設(shè)這個(gè)算法是問(wèn)題規(guī)模為n的函數(shù)f(n)，那么時(shí)間復(fù)雜度就記做：

T(n) = O(f(n))

O在表達(dá)式中代表著最壞的情況，這里最壞的情況就是n = 無(wú)窮大。

簡(jiǎn)單來(lái)說(shuō)，上述公式表達(dá)的含義就是在n趨于無(wú)窮大的時(shí)候，T(n) = f(n)。

f(n)指的是具體的函數(shù)，雖然對(duì)f(n)沒(méi)有規(guī)定，但是我們一般盡可能地去簡(jiǎn)化f(n)。

例如：O(n²+n+1)=O(3n²-n+5)=O(9n²+5)=O(n²)

注意大O中是攜帶一個(gè)常數(shù)C的，所以f(n)一般不加系數(shù)。

為什么可以這樣換算，為什么最后都可以換算為O(n²)？

這主要是因?yàn)楫?dāng)n趨于無(wú)限大時(shí)， n² 是遠(yuǎn)遠(yuǎn)大于 Cn的，也就是高次方項(xiàng)遠(yuǎn)遠(yuǎn)大于低次方項(xiàng)，導(dǎo)致低次方項(xiàng)完全可以忽略不計(jì)。

這就像是什么，我們把n²+3n+1想象為一棵樹(shù)的話，n²就是主干部分，3n+1就是一些細(xì)枝末節(jié)，是完全可以忽略的。

下面我們就來(lái)舉幾個(gè)示例，計(jì)算它們的時(shí)間復(fù)雜度：

第一題：

int x = 0;  //執(zhí)行1次
int y = 5;  //執(zhí)行1次
x = 10;     //執(zhí)行1次
int sum = x+y;  //執(zhí)行1次

以上四條語(yǔ)句的頻度均為1，該程序的執(zhí)行時(shí)間是一個(gè)與n完全無(wú)關(guān)的常數(shù)。算法的時(shí)間復(fù)雜度就是常數(shù)階，記做：T(n) = O(1)

假設(shè)這個(gè)算法有上千條語(yǔ)句，因?yàn)樗膱?zhí)行時(shí)間不會(huì)隨著n的增長(zhǎng)而變化，其執(zhí)行時(shí)間也不過(guò)是一個(gè)較大的常數(shù)。

此類(lèi)與n毫無(wú)關(guān)聯(lián)的算法的時(shí)間復(fù)雜度均可以記為：T(n) = O(1)。

第二題：

int number = 0;     //執(zhí)行一次
for(int i =0;i<n;i++){  //執(zhí)行n+1次，注意為什么是n+1，因?yàn)楫?dāng)條件不滿足時(shí)，也執(zhí)行了一次判斷
    number++;   //執(zhí)行n次
}

語(yǔ)句一的頻度為1。

語(yǔ)句二的頻度為n+1。

語(yǔ)句三的頻度為n。

所以上述代碼的時(shí)間復(fù)雜度為：T(n) =1 + n+1 + n = 2n+2。

接著當(dāng)n趨于無(wú)限大時(shí)，我們只需保留最高的次方項(xiàng)，即：T(n) = O(2n)，接著我們將系數(shù)省略到O中，即T(n)=O(n)。

第三題：

int number = 0;         //執(zhí)行1次
for(int i =0;i<n;i++){      //執(zhí)行n+1次
    for(int j =0;j<n;j++){  //執(zhí)行(n+1)*n次
        number++;   // 執(zhí)行n*n次
    }

}

第三題可能有些難度，是一個(gè)嵌套的for循環(huán)，我們來(lái)一句一句分析。

語(yǔ)句一是一個(gè)頻度為1的語(yǔ)句，和n無(wú)關(guān)，記為1。

語(yǔ)句二是一個(gè)外層for循環(huán)，執(zhí)行次數(shù)為n+1，1代表的是當(dāng)條件不滿足時(shí)，結(jié)束循環(huán)的那次操作。

語(yǔ)句三是嵌套的for循環(huán)，自身的執(zhí)行次數(shù)也是n+1，但是配合上外層的for循環(huán)，將會(huì)執(zhí)行n次嵌套for循環(huán)，所以語(yǔ)句三的頻度為：(n+1)*n。

語(yǔ)句四是嵌套for循環(huán)中的語(yǔ)句，一次嵌套for循環(huán)中的語(yǔ)句需要執(zhí)行n次，而嵌套for循環(huán)也需要執(zhí)行n次，所以語(yǔ)句四的頻度為：n*n。

那么整個(gè)程序的時(shí)間復(fù)雜度即為：T(n) = 1+ n+1 + (n+1) * n + n * n = 2n² +2n + 2。

當(dāng)n趨于無(wú)限大時(shí)，只保留最高次方項(xiàng)，并且省略系數(shù)，即：T(n) = O(n²);

通過(guò)上面三題的練習(xí)，各位看官對(duì)時(shí)間復(fù)雜度的計(jì)算過(guò)程應(yīng)該已經(jīng)了解了。

其實(shí)時(shí)間復(fù)雜度的真正計(jì)算，還是比較簡(jiǎn)單的，難在時(shí)間復(fù)雜度概念理解。

接下來(lái)我們來(lái)看一下常見(jiàn)的時(shí)間復(fù)雜度函數(shù)有哪些：

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

從圖中可以看出，隨著n的變化，時(shí)間復(fù)雜度各個(gè)函數(shù)的變化規(guī)律。

這些常見(jiàn)的時(shí)間復(fù)雜度大小排序如下：Ο(1)＜Ο(log₂n)＜Ο(n)＜Ο(nlog₂n)＜Ο(n²)＜Ο(n³)＜…＜Ο(2ⁿ)＜Ο(n!)

我們應(yīng)該盡可能使用時(shí)間復(fù)雜度小的算法，從而提升程序的運(yùn)行效率。

2. 空間復(fù)雜度

算法的空間復(fù)雜度指的是一個(gè)算法所消耗的存儲(chǔ)空間。

一個(gè)算法在計(jì)算機(jī)所占用的空間，由三方面決定：

• 存儲(chǔ)算法本身所占用的空間；
• 算法輸入輸出的數(shù)據(jù)所占用的空間；
• 算法在運(yùn)行過(guò)程中臨時(shí)占用的空間。

存儲(chǔ)算法本身所占用的空間與算法書(shū)寫(xiě)的長(zhǎng)短成正比，要壓縮這方面的存儲(chǔ)空間，就必須編寫(xiě)出較短的算法。

算法輸入輸出數(shù)據(jù)所占用的空間是由這個(gè)算法要解決的問(wèn)題決定的，針對(duì)同一問(wèn)題，它占用的空間不會(huì)隨著算法的變化而改變，但它確實(shí)占用著空間。

算法在運(yùn)行過(guò)程中臨時(shí)占用的空間會(huì)根據(jù)算法的不同而產(chǎn)生差異，也是我們最需要著重關(guān)心的一點(diǎn)。

有些算法只需要占用很少的臨時(shí)工作單元，并且不會(huì)隨問(wèn)題規(guī)模的變大而變大，我們稱這種算法是“就地”進(jìn)行的，是節(jié)省存儲(chǔ)的算法。

有些算法占用的臨時(shí)工作單元數(shù)與解決的問(wèn)題規(guī)模n有關(guān)，占用空間隨著n的增大而增大，當(dāng)n較大時(shí)，將占用較多的存儲(chǔ)單元，一些常見(jiàn)的排序算法就屬于這種情況，比如快速排序、歸并排序，屬于占用較多存儲(chǔ)空間的算法。

當(dāng)一個(gè)算法的空間復(fù)雜度不會(huì)隨著問(wèn)題規(guī)模的變化而變化時(shí)，可表示為O(1)。

當(dāng)一個(gè)算法的空間復(fù)雜度與問(wèn)題規(guī)模n呈線性比例關(guān)系時(shí)，可表示為O(n)。

同理，其他變化關(guān)系也可以推導(dǎo)出來(lái)。同時(shí)間復(fù)雜度相比，空間復(fù)雜度的分析還是比較簡(jiǎn)單的。

3. 其他

除了上述兩條評(píng)定規(guī)則外，評(píng)價(jià)一個(gè)算法的質(zhì)量還有其他幾個(gè)因素：

• 正確性：算法的正確性是評(píng)價(jià)一個(gè)算法優(yōu)劣最重要的標(biāo)準(zhǔn)！這個(gè)算法的結(jié)果是錯(cuò)誤的，那么這個(gè)算法毫無(wú)意義。
• 可讀性：可讀性指的是人們理解這個(gè)算法的難易程度，當(dāng)時(shí)間復(fù)雜度與空間復(fù)雜度相同的情況下，當(dāng)然要選擇易于人們理解的算法。
• 健壯性：健壯性是指一個(gè)算法對(duì)不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。

總結(jié)

本文是算法最基本的一些知識(shí)，看完本文，需要你完全理解下圖的含義：

排序算法復(fù)雜度

后續(xù)還會(huì)針對(duì)算法，做一些更深入的分析，感謝各位看官的瀏覽。

鞠躬。

感謝

百度百科

算法的時(shí)間復(fù)雜度和空間復(fù)雜度-總結(jié)