嵌套循环的大O复杂度
提问于 2015-03-16 17:28:59
for (i = 0; i < 2*n; i += 2)
{
for (j=n; j > i; j--)
//some code that yields O(1)
}我原以为上面的内容会产生n*log(n)，但我看到另一个消息来源说，这确实是n^2的复杂性。请向我解释一下它是什么，以及我将来如何处理这样的问题。
回答 2
Stack Overflow用户
回答已采纳
发布于 2015-03-16 17:31:42
由于大O是上界的，所以N*N永远是<= N^2，从而产生O(N*2)。答案是正确的
Stack Overflow用户
发布于 2015-03-16 17:32:30
您有一个依赖于n的循环，在该循环中有另一个也依赖于n的循环，因此得到的O是O(n*n)，即O(n^2)。
大O只提供了算法增长率的上界。因此，所有常数因子都被丢弃。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29089864
复制相关文章
点击加载更多
腾讯云开发者
