算法的最壞情況與平均運行時間之間的關係

Question

假設A（n）是算法的平均運行時間，W（n）最差。

A(n) = O(W(n)) 

是否正確？

Answer 1

Big O符號有點棘手，因爲它只定義了給定算法的執行時間的上限。

這是什麼意思，如果f(x) = O(g(x))那麼對於其他函數h(x)這樣g(x) < h(x)你將有f(x) = O(h(x))。問題是，那些過時的執行時間是否有用？而明確的答案根本就不是。通常你會得到的是「最小」 上限，但這並不是嚴格要求的定義，所以你可以玩弄它。

你可以得到一些更嚴格的使用其他符號，如大西塔，你可以閱讀here約束。

所以，回答你的問題是肯定的，A(n) = O(W(n))，但這並不會給算法的任何有用的信息。

Answer 2

如果你提到A（n）和W（n）是函數 - 那麼，是的，你可以在普通情況下這樣做 - 這是因爲big-o formal definition。

注意，在上big-o方面有沒有意義，這樣的行爲方式 - 因爲它使真正的複雜性更差的理解。 （一般來說，3例 - 最差的，平均而言，最好的 - 正是目前顯示的複雜性更清晰）

Answer 3

我不確定你要問什麼，但牢記以下。

用於顯示平均和最差情況下運行時間複雜度之間的差異的典型算法是快速排序，選擇的樞軸選項很差。

平均與未排序的數據的隨機樣本，運行時的複雜性是n log(n)。但是，對於從列表的前端/末端取得樞軸的已有數據集，運行時複雜度爲n^2。

Answer 4

是的，這樣說並不是一個錯誤。

人們用漸近記法來傳達運行時間在特定的情況下在輸入方面sizes.To比較最壞的情況下複雜的平均情況複雜度的增長並沒有提供多少洞察理解上兩種情況中的作用的增長。
雖然沒有錯，但它不能提供比我們已知的更多信息。