有些书指出 theta 表示法称为平均情况，而另一些书则指出 theta 不是平均情况。
如果 theta 不是平均情况，那么什么是算法的平均情况？
O、Ω 和 θ 符号实际上与算法的最佳/平均/最差情况无关。它们是表达函数渐近行为的方法，无论函数是什么。
f(n) = O(g(n)) 意味着 f 的增长速度不会快于 g。 g 是上限，无论是否严格。
f(n) = Ω(g(n)) 意味着 f 的增长速度不会慢于 g。 g 是下界，无论是否严格。
f(n) = θ(g(n)) 意味着 f 的增长速度与 g 一样快。 g 是上界和下界的紧界。
那么，算法的最佳/平均/最差运行时间是元素数量的函数，通常有 O、Ω、θ 表示。
在分析特定算法时，人们通常能够推导出最坏情况的 O 界，无论该 O 界是紧的还是不紧的。此外，如果付出更多的努力，平均时间也会受到限制。通常你不关心最好的时间。
然后，在分析给定问题（无论解决该问题的任何特定算法）时，有时可以建立运行时间的绝对下限，即最佳时间（紧或不紧）的 Ω 界限。平均时间的下限有时是可能的，但技术性很强。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
