为什么该算法的Big-O复杂度为O（n ^ 2）？ [英] Why is the Big-O complexity of this algorithm O(n^2)?

问题描述

我知道此算法的big-O复杂度是 O（n ^ 2），但我不明白为什么。

I know the big-O complexity of this algorithm is O(n^2), but I cannot understand why.

int sum = 0; 
int i = 1; j = n * n; 
while (i++ < j--) 
  sum++;

即使我们设置 j = n * n 在开始时，我们在每次迭代过程中增加i并减少j，所以迭代的结果数量是否应该不小于 n * n ？

Even though we set j = n * n at the beginning, we increment i and decrement j during each iteration, so shouldn't the resulting number of iterations be a lot less than n*n?

推荐答案

在每次迭代中，您递增 i 并递减 j 等效于将 i 递增2。因此，迭代总数为n ^ 2/2，而仍为O（n ^ 2 ）。

During every iteration you increment i and decrement j which is equivalent to just incrementing i by 2. Therefore, total number of iterations is n^2 / 2 and that is still O(n^2).

这篇关于为什么该算法的Big-O复杂度为O（n ^ 2）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！