找出大O表示法的运行时间
找出大O表示法的运行时间
提问于 2011-02-14 08:28:00
1) for (i = 1; i < n; i++) { > n
2) SmallPos = i; > n-1
3) Smallest = Array[SmallPos]; > n-1
4) for (j = i+1; j <= n; j++) > n*(n+1 -i-1)??
5) if (Array[j] < Smallest) { > n*(n+1 -i-1 +1) ??
6) SmallPos = j; > n*(n+1 -i-1 +1) ??
7) Smallest = Array[SmallPos] > n*(n+1 -i-1 +1) ??
}
8) Array[SmallPos] = Array[i]; > n-1
9) Array[i] = Smallest; > n-1
}我知道大O符号是n^2 (我的错是它不是n^3)
我不确定在4-7行有人愿意帮忙吗？我不确定如何获得第二个循环的输出，因为j=i +1随着i的变化，j也会变化
还有，对于第4行，ans假设为n(n+1)/2 -1，我想知道为什么，因为我永远得不到
我并不是真的要解决大O问题，我只是想做一些步骤，把大O当做常量，变量在大O符号中省略掉。
回答 3
Stack Overflow用户
发布于 2011-02-14 08:31:11
我会说这是O(n^2) (尽管正如Fred在上面指出的，O(n^2)是O(n^3)的一个子集，所以说它是O(n^3)是没有错的)。
请注意，通常没有必要计算每一行的执行次数；由于Big-O表示法丢弃了低阶项，因此只关注执行次数最多的部分(通常在最里面的循环中)就足够了。
因此，在您的示例中，所有循环都不受Array中的值的影响，因此我们可以安全地忽略所有这些。最里面的循环运行(n-1) + (n-2) + (n-3) + ...次；这是一个arithmetic series，因此在n^2中有一项。
Stack Overflow用户
发布于 2011-02-14 08:33:31
两个for()循环，外部循环从1到n，内部循环在1..n到n之间运行，这使得它是O(n^2)。
如果你“把它画出来”，它将是三角形的，而不是矩形的，所以O(n^2)虽然是真的，但它隐藏了一个事实，即恒定因子项比内部循环也从1迭代到n时要小。
Stack Overflow用户
发布于 2011-02-14 08:33:49
它是O(n^2)。
对于外部循环的n次迭代中的每一次，在内部循环中都有n次迭代。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4987894
复制相关文章
相似问题
腾讯云开发者
