为什么这个算法的Big-O复杂度是O(n^2)？
为什么这个算法的Big-O复杂度是O(n^2)？
提问于 2015-11-23 03:02:28
我知道这个算法的大O复杂度是O(n^2)，但我不明白为什么。
int sum = 0;
int i = 1; j = n * n;
while (i++ < j--)
sum++;即使我们在开始时设置了j = n * n，我们在每次迭代中递增i和递减j，因此产生的迭代次数不应该比n*n少得多
回答 5
Stack Overflow用户
回答已采纳
发布于 2015-11-23 03:07:35
在每次迭代中，您递增i和递减j，这相当于仅将i递增2。因此，迭代的总次数是n^2 /2，这仍然是O(n^2)。
Stack Overflow用户
发布于 2015-11-23 03:10:24
您将恰好有奇数循环迭代(如果n为奇数，则为(n*n-1)/2 )。在大O符号中，我们有O((n*n-1)/2) = O(n*n/2) = O(n*n)，因为常量因子“不算数”。
Stack Overflow用户
发布于 2015-11-23 10:10:07
你的算法等同于
while (i += 2 < n*n)
...这是与O(n^2)相同的O(n^2/2)，因为大的O复杂度并不关心常量。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/33858889
复制相关文章
相似问题