如何计算平均复杂度

算法的平均复杂度是如何计算的？最坏的情况是明显的，也是最好的，但平均值是如何计算的？如何计算平均复杂度

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

如何计算平均复杂度

回答

相关问题