演算法中上界和下界分別是指什麼

1樓：June

假如當前機場安檢人數有10人，你要在這個長隊中找乙個人(你確定你要找的人一定在10個人中)

最好的情況是第乙個人就是你要找的人 = 下界

最壞的情況是最後一人才是你要找的人 = 上界 = 大O

2樓：[已重置]

大多數情況下我們並不需要知道演算法具體的執行時間，其他操作反正都是確定的常數，只需要知道這個時間和輸入的規模是什麼關係，也就是當非常大的時候，其他常量的影響可以忽略。我們甚至根本不需要知道具體是什麼關係，只需要知道關於這個的時間複雜度在什麼數量級就可以了，這個時候我們的度量就是漸近複雜度。

首先我們要弄清三種漸近複雜度： Big-Theta(),Big-Omega(),Big-O()

簡單來說表示漸近上界，表示漸近下界，表示漸近邊界

具體的數學表達裡，約定以下設定常數,,均為正數，集合中的冒號後面的描述的前提是存在乙個，對於任意n_0" eeimg="1"/>冒號後面的約束都成立。

這裡的是個集合，但是為了表示方便也可以表示某個具體的漸近函式。

如果,那麼這時可以說是的asymptotic tight bound(這東西用中文怎麼說來著我忘了，反正你們這洋文好的人多的很吶）

同理可定義和，當然根據這個定義不難推出的充要條件是且，也就是既是上界又是下界的時候就是漸近確界..表示的就是一種較為準確的數量級，這個有點類似於微積分中的幾階無窮小的概念。

舉個例子：

，，，，

因為只關心數量級，所以係數都取為1

2.執行時

如果我們預先欽定了乙個演算法的執行時間是可以預料的，也就是確定的，比如這樣乙個函式：

time_t

wearHighBelt2Prolong

(time_t

hasi

,intn,

time_t

hislife

)return

hislife;}

這裡你可以理解為或者，總之是乙個關於hasi陣列的長度的一次函式。那我們自然容易看出漸近確界是。但實際上很多演算法很複雜，涉及一些條件判斷語句來決定某個操作要不要執行，最終執行多少次，這時候它的執行時間就是不可預料的，必須考慮輸入的程序。

time_t

wearRedClothes2Prolong

(time_t

hasi

,intn,

time_t

hislife)}

else}}

}return

hislife;}

這裡新增乙個簡單的分支結構，就必須考慮hislife的情況了，如果大於301那麼時間代價就是級的，如果小於301，時間代價就是級的。

這時候我們就知道為什麼除了緊確界以外，還要引入和作為上下界了。因為對於無法具體寫出確定的表達（無分段）的代價函式時，比如需要依靠輸入的情況進行分段表達的函式，是不存在的。

用的比較少，「不少於」的描述，「最好情況」的假設，對於複雜度沒什麼意義，但是它的對偶概念用的就很多了，因為往往要估計的是最壞情況，也就是說對於wearRedClothes2Prolong函式來說，我們說它的時間複雜度是而非，我們往往估算複雜度的時候用的都是上界，按最壞的情況打算。

但是呢，即使是上界也是應該對各種輸入和其他情況分別進行描述的，考慮各自情況中的最壞的情況，所以還是用的上界來描述，比如各常見演算法/操作的複雜度http://

很慚愧，只做了一些微小的工作。