算法的例子有不同的最坏情况上界、最坏情况下界和最佳情况界。
算法的例子有不同的最坏情况上界、最坏情况下界和最佳情况界。
提问于 2014-09-14 16:34:59
对于一组最坏的情形，A是否有算法A，使A有不同的最坏情形上界和最坏情形下界？此外，对于某些输入集，它应该有不同的最佳情况界，而不等于任何最坏情况下的界。
例如，假设H是一种假设算法，使得H具有最坏情况下界Ο(n^3)、最坏情况下界Ω(n^2)和最佳情况运行时间Θ(n)。
让我知道，上述情况是否真的有意义？
谢谢:)
回答 2
Stack Overflow用户
回答已采纳
发布于 2014-09-14 17:03:53
下面是一个不太自然但可能更令人满意的H定义。此函数以相当愚蠢的方式计算输入列表之和的立方体。
def H(lst):
s1 = 0
for x in lst:
s1 += x
if s1 == 0:
return 0
elif len(lst) % 2 == 0:
s2 = 0
for x in lst:
for y in lst:
s2 += x * y
return s1 * s2
else:
s3 = 0
for x in lst:
for y in lst:
for z in lst:
s3 += x * y * z
return s3最好的情形界是Theta(n).形式O(n^k)最紧的最坏情况上界是O(n^3).形式Ω(n^k)的最坏情况下界是Ω(n^2).
然而，请注意，在最坏情况下，任何形式的最紧界都是Θ(f(n))，其中f(2m) = m^2，f(Θ)= m^3。
Stack Overflow用户
发布于 2014-09-14 16:41:29
按照你描述的方式，选择任何二次排序算法，比如气泡排序：
- 最坏的情况下，上界可以说是
O(n^3)。 - 最坏的情况下界可以说是
Ω(n^2)。 - 最好的运行时间可以说是
Θ(n)，当输入已经排序，并且在启动算法之前用一次传递来检查这一点，或者在这种情况下使用提前终止算法的优化。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/25835500
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号