如何計算平均複雜度

算法的平均複雜度是如何計算的？最壞的情況是明顯的，也是最好的，但平均值是如何計算的？如何計算平均複雜度

2014-02-13 Yoda

這裏是我曾計算的預期runtine答案： - http://stackoverflow.com/questions/21719141/algorithm-analysis-expected-running-time-of-recursive-function-based-on- a-rng/21728256＃21728256使用期望 –

與之相關的是，從具有N個節點的所有樹的集合中隨機選擇的樹的預期深度與通過向隨機地點添加節點而生成的樹的預期深度不同。類似的概念使計算算法的「平均數」和「期望」非常棘手，除非你清楚地表明你正在測量的是什麼。 –

通過考慮給定大小的所有可能輸入並在所有這些輸入中指出各個測量的平均值的漸近界，可以找到平均性能（時間，空間等）複雜度。

例如，一種排序的平均「比較次數」複雜度可以通過考慮所有N！大小爲N的輸入的排列和在所有這些輸入中執行的平均比較數量的界限。

I.e.這是所有可能的N的比較數的總和！輸入除以N！

由於所有可能輸入的平均性能等於相同性能測量的預期值，因此平均性能也稱爲預期性能。

來源

2014-02-13 01:17:29 Gene

Quicksort提供了一個計算平均運行時性能的有趣的非平凡示例。正如你所看到的，數學可能會變得相當複雜，所以不幸的是，我不認爲有一個計算平均表現的通用方程。

來源

2014-02-13 02:08:30

根據它們的概率計算所有可能輸入和取和的加權和的複雜度。這也被稱爲期望的runtine（類似於概率期望）。

ET(I) = P(X=I1)*T(I1) + P(X=I2)*T(I2) + P(X=I3)*T(I3).......

來源

2014-02-13 04:35:52

如何計算平均複雜度

回答

相關問題