944
《算法技術手冊》一2.3.1 最壞情況
2.3.1 最壞情況
對於任一特定值n，算法或者程序在處理所有規模為n的樣本時的執行時間可能會發生巨大的變化。對於一個給定的程序和一個給定的值，最壞的執行時間就是處理所有規模為n的數據所需要的最長執行時間。
之所以關注算法的最壞情況，是因為它通常是最容易分析的情況。此外，它還能夠說明程序在各種場景下到底會有多慢。
更正式地說，如果Sn是所有規模為n的問題樣本si構成的集合，t()代表算法對於每一個問題樣本所需要的執行時間，那麼算法在最壞情況下的執行時間為：t(si)對於所有si∈Sn的最大值。我們將Sn在最壞情況下的性能記作Twc(n)。Twc(n)的增長率定義了算法在最壞情況下的複雜度。
一般來說，通過計算每一份數據si來判定算法在哪份數據上表現最壞，這種做法是不切實際的——沒有足夠的資源。相反，算法分析人員會精心設計出能讓算法的性能落入最壞情況的問題樣本。
最後更新：2017-09-19 16:02:40