问最佳案例分析，嵌套循环算法
EN

Stack Overflow用户

提问于 2014-02-04 21:11:13

回答 1查看 2.3K关注 0票数 0

在这个特定的算法中，bese的情况是什么？从严格意义上说，这是否比最坏的情况更好呢？在我看来，这两者似乎是一样的。

sum = 0
for (i=1; i <= n; i++)
    for (j=i+1; j <= n; j++)
        sum++

回答已采纳

发布于 2014-02-04 21:16:07

“最佳情况”的概念只有在算法的时间复杂度(或空间复杂度)根据输入而变化时才适用。例如，一个快速排序的简单实现在O(n log )时间内运行，在最佳情况下(当枢轴是中间的)，而O(n^2)最坏的情况(当枢轴是最小值或最大值时)。

你的算法只有一个输入: n，它的时间复杂度是O(n^2)，不考虑n，所以没有特殊的“最佳情况”。

请注意，您可以在恒定时间内产生相同的结果：

sum = (n * n - n) / 2

票数 2

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/21563488

复制

相似问题

问最佳案例分析，嵌套循环算法EN