最好最壞和平均情況下的性能分析

現(xiàn)在有一個(gè)問題，對(duì)于所有的輸入來(lái)說(shuō)，前面得到的結(jié)果是否都成立呢？第二種排序法在少量字符串的時(shí)候性能也許是最好的。但是，輸入數(shù)據(jù)有很多地方可能變化：

輸入數(shù)據(jù)可能有1 000 000個(gè)字符串。算法如何處理如此大規(guī)模的數(shù)據(jù)？

輸入數(shù)據(jù)可能會(huì)是部分有序狀態(tài)，也就是說(shuō)，幾乎所有的元素所在的位置離最終位置并不是很遠(yuǎn)。

輸入數(shù)據(jù)可能包含重復(fù)的值。

無(wú)論輸入數(shù)據(jù)的規(guī)模n是多少，輸入數(shù)據(jù)都可以從一個(gè)小得多的數(shù)據(jù)集擴(kuò)展而來(lái)，不過(guò)會(huì)有相當(dāng)多的重復(fù)值。

雖然從圖2-2上來(lái)看，第四種排序法在排序n個(gè)亂序字符串的時(shí)候是最慢的，但是處理已經(jīng)排序的數(shù)據(jù)卻是最快的。但是，隨著n的增長(zhǎng)，第四種排序法的領(lǐng)先優(yōu)勢(shì)消失得非常快，我們從圖2-3上可以看到，在對(duì)16個(gè)亂序的字符串進(jìn)行排序時(shí)，第四種排序法就已經(jīng)失去領(lǐng)頭羊的位置了。

?

?

盡管如此，假設(shè)一個(gè)包含n個(gè)字符串的輸入，并且這個(gè)輸入已經(jīng)是幾乎有序，其中n/4個(gè)字符串（占總字符串的25%）被交換到僅僅是離最終位置4個(gè)元素。最終結(jié)果如圖2-4所示，我們看到第四種排序法性能表現(xiàn)遠(yuǎn)遠(yuǎn)好于其他的排序算法。

?

我們得到這樣一個(gè)結(jié)論，對(duì)于許多問題來(lái)說(shuō)，并不存在單一的最優(yōu)算法。選擇一個(gè)算法需要對(duì)問題有著充分的理解，并知道這個(gè)問題將要處理數(shù)據(jù)規(guī)模的概率分布情況，還有算法的實(shí)際行為也必須要考慮到。

在這里我們提供一些指導(dǎo)，算法通常會(huì)分成三種情況進(jìn)行分析：

最壞情況

定義一類輸入，在這類輸入下，算法表現(xiàn)出了最壞的運(yùn)行性能。算法設(shè)計(jì)人員需要明白，這類輸入的共同性質(zhì)阻止了算法高效地運(yùn)行，而不只是針對(duì)特定的輸入。

平均情況

平均情況是表示算法在隨機(jī)給定的數(shù)據(jù)上期望的執(zhí)行情況。通俗地說(shuō)，一些輸入可能會(huì)在某些特殊情況下耗費(fèi)程序大量的時(shí)間，但是大部分的輸入并不會(huì)這樣。這個(gè)衡量標(biāo)準(zhǔn)描述了用戶對(duì)算法性能的期望。

最好情況

定義一類輸入，算法在這類輸入下表現(xiàn)出了最好的運(yùn)行性能。對(duì)于這類輸入來(lái)說(shuō)，算法只進(jìn)行很少的計(jì)算。不過(guò)在實(shí)際情況下，最好情況很少出現(xiàn)。

通過(guò)分析三種情況，大致了解了算法的性能，那么接下來(lái)你需要為將要面臨的問題選擇一個(gè)算法。

最壞情況

大多數(shù)問題都可能會(huì)處理一些比n大的數(shù)據(jù)。任意給定一個(gè)n，算法或者程序在處理所有規(guī)模為n的數(shù)據(jù)，其性能可能會(huì)動(dòng)態(tài)地發(fā)生變化。給定一個(gè)程序和n，這個(gè)程序的最壞運(yùn)行時(shí)間就是處理所有規(guī)模為n的數(shù)據(jù)所需要的最長(zhǎng)運(yùn)行時(shí)間。

我們也看到，最壞情況是對(duì)整個(gè)世界的一個(gè)悲觀的分析。但是我們還是非常關(guān)注最壞情況，因?yàn)?#xff1a;

追根刨底的欲望

這通常是對(duì)一個(gè)算法復(fù)雜度的最早的分析。

實(shí)際運(yùn)行時(shí)的限制

如果你需要設(shè)計(jì)一個(gè)系統(tǒng)，協(xié)助外科醫(yī)生進(jìn)行體外循環(huán)心臟手術(shù)，那么長(zhǎng)時(shí)間的運(yùn)行（即使這種情況是不經(jīng)常發(fā)生）當(dāng)然不可能接受。

更正式地說(shuō)，如果Sn是數(shù)據(jù)集合si中規(guī)模為n的子集，t表示算法在每一份數(shù)據(jù)上的運(yùn)行時(shí)間，那么最壞情況下，對(duì)于所有si∈Sn，算法在Sn上的運(yùn)行時(shí)間是t(si) 的最大值。我們將在Sn下的最長(zhǎng)時(shí)間記做Twc(n)，Twc(n) 的增長(zhǎng)率表示算法在最壞情況下的復(fù)雜度。

一般來(lái)說(shuō)，沒有足夠的資源來(lái)計(jì)算每一份數(shù)據(jù)si，然后檢查算法在哪份數(shù)據(jù)上表現(xiàn)最壞。于是，給定算法的描述，算法分析人員總是想方設(shè)法地精心準(zhǔn)備可能會(huì)導(dǎo)致最壞情況的輸入數(shù)據(jù)。

平均情況

現(xiàn)在要設(shè)計(jì)一個(gè)支持n個(gè)電話的電話系統(tǒng)，n是一個(gè)非常大的數(shù)目，要求在最壞情況下，即n/2位用戶同時(shí)呼叫另外n/2位用戶時(shí)，這個(gè)系統(tǒng)也能夠正確地處理數(shù)據(jù)。雖然這個(gè)系統(tǒng)不會(huì)由于過(guò)載而崩潰，但需要花費(fèi)過(guò)高的代價(jià)構(gòu)造這樣的情況。而且，n/2位用戶同時(shí)呼叫另外n/2位用戶發(fā)生的概率極小。也許可以設(shè)計(jì)一個(gè)花費(fèi)較小的系統(tǒng)在過(guò)載的情況下很少會(huì)（或者從不）崩潰。但是我們還是必需借助數(shù)學(xué)工具來(lái)計(jì)算這個(gè)概率問題。

對(duì)于一個(gè)n個(gè)樣本的數(shù)據(jù)集合，我們用一個(gè)概率分布Pr表示樣本的出現(xiàn)概率，單個(gè)樣本的出現(xiàn)概率為0到1，所有樣本的概率的和為1。如果Sn是n個(gè)樣本的數(shù)據(jù)集合，那么：

?

如果t表示算法在單個(gè)樣本的執(zhí)行時(shí)間，那么在Sn上的平均運(yùn)行時(shí)間是：

??

也就是說(shuō)，在樣本si的實(shí)際執(zhí)行時(shí)間，t(si) 將會(huì)與概率加權(quán)。如果Pr{si}=0，那么t(si) 的實(shí)際值將不會(huì)影響程序的期望運(yùn)行時(shí)間。我們用Tac(n) 表示算法在Sn上的平均運(yùn)行時(shí)間，那么Tac(n) 的增長(zhǎng)率表示算法在平均情況下的復(fù)雜度。

回憶一下，當(dāng)我們描述時(shí)間或者工作量的增長(zhǎng)率時(shí)，我們一直忽視了常數(shù)，所以我們認(rèn)為順序搜索n個(gè)元素的平均情況為：

??

探測(cè)（符合我們之前的假設(shè)），按照慣例，在符合這些假設(shè)的前提下，期望順序搜索能夠處理線性或者是n階的元素。

最好情況

知道算法的最好情況是非常有用的，即便這種情況很少發(fā)生。在很多情況下，最好情況能讓我們看到算法的最優(yōu)狀況。例如，線性搜索的最好情況是當(dāng)它在n個(gè)元素中搜索v的時(shí)候，第一個(gè)元素恰好就是要找的那個(gè)。一個(gè)稍微有些不同的算法，我們叫做計(jì)數(shù)搜索（Counting Search），在n個(gè)元素中搜索v，并且記錄v在表中出現(xiàn)的次數(shù)。如果v的計(jì)數(shù)是0，那么這個(gè)值是不存在的，所以會(huì)返回false，否則返回 true。注意，計(jì)數(shù)搜索總是會(huì)搜索整個(gè)表，因此，它的最壞情況是O(n)（和順序搜索一樣），最好情況還是O(n)，所以我們不能夠使用這個(gè)算法，因?yàn)樗淖詈没蛘咂骄闆r沒有改善性能。

總結(jié)

以上是生活随笔為你收集整理的最好最坏和平均情况下的性能分析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。