討厭算法的程序員系列入口

時(shí)間資源

上一篇，我們知道了如何用循環(huán)不變式來(lái)證明算法的正確性，本篇來(lái)看另一個(gè)重要方面：算法分析。分析算法的目的，是預(yù)測(cè)算法所需要的資源。資源不僅是指內(nèi)存、CPU等硬件資源，人們更關(guān)注的是計(jì)算時(shí)間（時(shí)間資源）。

到這里可能會(huì)產(chǎn)生一個(gè)疑問(wèn)，計(jì)算時(shí)間與硬件資源強(qiáng)相關(guān)，不同的硬件配置下計(jì)算時(shí)間就不同。那么如何來(lái)衡量算法的效率呢？

答案是必須有一個(gè)穩(wěn)定的硬件模型。在此基礎(chǔ)上，才能屏蔽掉硬件配置不同導(dǎo)致的算法運(yùn)行時(shí)間的差異，從而單單顯露出算法本身的優(yōu)劣。

算法分析的環(huán)境模型

《算法導(dǎo)論》中，明確的定義了該模型：通用的單處理器/RAM計(jì)算模型（RAM，隨機(jī)訪問(wèn)）。這是大多數(shù)講算法的書(shū)里沒(méi)有提到的重要前提。

模型指標(biāo)：

• 單處理器；
• RAM；
• 基于真實(shí)計(jì)算機(jī)中常見(jiàn)的指令：算術(shù)指令（加法、減法、乘法、除法、取余、向下取整、向上取整），數(shù)據(jù)移動(dòng)指令，控制指令；
• 指令一條一條的執(zhí)行，無(wú)并發(fā)執(zhí)行；
• 假設(shè)每條指令所需時(shí)間都為常量，2^k指數(shù)操作也看成一個(gè)常量時(shí)間操作（k是一個(gè)足夠小的正整數(shù)）；
• 不關(guān)心數(shù)據(jù)的精度，假設(shè)每個(gè)數(shù)據(jù)字有最大長(zhǎng)度限制；
• 不區(qū)分內(nèi)存層次——高速緩存和虛擬內(nèi)存。

所有算法的運(yùn)行，都基于上述環(huán)境模型，比較的基礎(chǔ)就有了。

算法分析基礎(chǔ)

算法分析的兩個(gè)重要概念就是輸入規(guī)模和運(yùn)行時(shí)間。

輸入規(guī)模

拿插入排序舉例，排序1000個(gè)數(shù)肯定比排序10個(gè)數(shù)需要更長(zhǎng)的時(shí)間。這里的1000和10就是不同的輸入規(guī)模。

輸入規(guī)模的度量，對(duì)于不同的問(wèn)題其度量的單位是不同的。對(duì)于插入排序來(lái)說(shuō)，其度量是數(shù)組中數(shù)的個(gè)數(shù)n。對(duì)于某個(gè)算法的輸入是一個(gè)圖（Graph）的，則輸入規(guī)?？梢杂迷搱D中的頂點(diǎn)數(shù)n₁和邊數(shù)n₂——兩個(gè)量來(lái)描述。每個(gè)具體問(wèn)題，我們都要指出所使用的輸入規(guī)模度量。

運(yùn)行時(shí)間

運(yùn)行時(shí)間的度量，并非我們所用的時(shí)、分、秒。前面的環(huán)境模型中，我們假設(shè)了每條指令所需時(shí)間都是常量，這里我們?cè)俑M(jìn)一步，執(zhí)行第i行代碼的每次執(zhí)行需要時(shí)間為c_i,無(wú)論該行代碼循環(huán)多少次，每次都一樣。那么程序運(yùn)行的總時(shí)間就是，每行代碼執(zhí)行時(shí)間c_i之和。

算法需要的時(shí)間與輸入的規(guī)模同步增長(zhǎng)，所以通常把一個(gè)程序的運(yùn)行時(shí)間描述成其輸入規(guī)模的函數(shù)。

插入排序算法的分析

有了“輸入規(guī)?！焙汀斑\(yùn)行時(shí)間”兩個(gè)基本概念，我們?nèi)砸?a href="http://www.itdecent.cn/p/efb81b9c6a17" target="_blank">插入排序為例，對(duì)其偽碼進(jìn)行分析。具體做法就是：計(jì)算每行代碼執(zhí)行時(shí)間c_i之和，得出輸入規(guī)模與運(yùn)行時(shí)間的關(guān)系。

以下逐行分析代碼的執(zhí)行時(shí)間：

代碼分析

要點(diǎn)說(shuō)明：

• for或while循環(huán)，“循環(huán)頭”中的測(cè)試執(zhí)行的次數(shù)，由于退出時(shí)的測(cè)試，會(huì)比其“循環(huán)體”執(zhí)行的次數(shù)多1次；
• 代碼的5~7行，是for循環(huán)中嵌套的while循環(huán)，因此是由外層for的循環(huán)變量j從2到n求t_j的和；
• t_j是while“循環(huán)頭”的執(zhí)行次數(shù)；
• t_j-1，表示“循環(huán)體”的執(zhí)行次數(shù)比“循環(huán)頭”少1次。

運(yùn)行時(shí)間

每行代碼的運(yùn)行時(shí)間，乘以每行代碼運(yùn)行的次數(shù)，再對(duì)其求和，就能得到總運(yùn)行時(shí)間。同時(shí)，也得到了輸入規(guī)模n與運(yùn)行時(shí)間T(n)的關(guān)系。

算法運(yùn)算時(shí)間

最好情況

運(yùn)行時(shí)間雖然得到了，但是我們很難從復(fù)雜的函數(shù)表達(dá)中看出規(guī)律，因此需要進(jìn)一步的簡(jiǎn)化。

一個(gè)簡(jiǎn)化的方向就是考慮其最好情況。也就是說(shuō)，排序算法執(zhí)行之前，輸入已經(jīng)是排序好的數(shù)組，那么t_j應(yīng)為1。t_j=1是因?yàn)閣hile的“循環(huán)頭”還是要做1次測(cè)試的，while循環(huán)體的代碼是執(zhí)行不到的。將t_j代入：

最好情況

此時(shí)的表達(dá)式就清晰多了,因?yàn)閏_i是常量，我們?cè)俅螌⑵浜?jiǎn)化成T(n)=an+b，這不就是個(gè)線性函數(shù)嗎？線性函數(shù)具有的一切特性都可以用于分析“輸入規(guī)模”與“運(yùn)行時(shí)間”的關(guān)系。

最壞情況

考慮過(guò)最好情況，當(dāng)然還需要考慮最壞情況。最壞情況就是，排序之前，數(shù)組是按照降序排列的（排序之后升序）。具體的說(shuō)，while“循環(huán)頭”的每次測(cè)試都成立直到i≤0，“循環(huán)體”每次都要執(zhí)行。此時(shí)，t_j=j，將其代入：

最壞情況

再次簡(jiǎn)化，就可以得到T(n)=an²+bn+c，它是一個(gè)二次函數(shù)，隨著輸入規(guī)模n的增大，T(n)會(huì)急劇的增加。

小結(jié)

此時(shí)，我們對(duì)于插入排序算法的分析基本結(jié)束了?？赡苡腥藭?huì)問(wèn)，只分析了最好和最壞的情況，那“平均情況”是什么？

《算法導(dǎo)論》明確的解釋說(shuō)，我們大多數(shù)時(shí)候應(yīng)該關(guān)注最壞情況的運(yùn)行時(shí)間，理由是：

• 最壞情況給出了任何輸入運(yùn)行時(shí)間的一個(gè)上限（做最壞的打算）；
• 對(duì)某些算法，最壞情況經(jīng)常出現(xiàn)，比如檢索一條不存在的信息；
• “平均情況”往往與最壞情況大致一樣差。

當(dāng)然也有特別的情況，就是“平均情況”可以用“概率分析”來(lái)描述，以后介紹“隨機(jī)化算法”時(shí)再討論。

上一篇 2 證明算法的正確性
下一篇 4 時(shí)間復(fù)雜度

共享協(xié)議：署名-非商業(yè)性使用-禁止演繹（CC BY-NC-ND 3.0 CN）
轉(zhuǎn)載請(qǐng)注明：作者黑猿大叔（簡(jiǎn)書(shū)）