为什么这个算法的Big-O复杂度为O(n ^ 2)？

Question

我知道这个算法的大O复杂性O(n^2),但我不明白为什么.

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

即使我们j = n * n在开始时设置,我们在每次迭代期间递增i并递减j,所以迭代的结果数量是否应该小于n*n？

Answer 1

在每次迭代期间,您递增i和递减j,这相当于仅递增i2.因此,迭代的总数是n ^ 2/2,并且仍然是O(n ^ 2).

Answer 2

big-O复杂性忽略了系数.例如:O(n),O(2n)和O(1000n),都是相同的O(n)运行时间.同样,O(n^2)并且O(0.5n^2)都是O(n^2)运行时间.

在你的情况下,你实际上每次通过循环将循环计数器递增2(因为j--效果相同i++).所以你的运行时间是O(0.5n^2),但这与O(n^2)你删除系数时的相同.

@djechlin O(n²)不是O(n³),但它是它的一个子集. (8认同)
在你的扩展解释的上下文中,你确实在等于O(n ^ 2)= O(n ^ 3)时是正确的,但是在线程顶部的原始一个衬里没有得到很好的解释.你可以成为房间里最世界级的大人物,但如果你不能很好地表达自己的想法,那么你的知识就毫无用处.如果你认为其他所有人都不同意你作为巨魔的精神,那么你已经脱离了重要的外部学习来源,如果你这样做,你就不会保留你的顶级大人物.只是一些值得思考的东西. (4认同)
@djechlin你似乎花了很多时间来检查这个问题和"上学"的人.如果只花几秒钟来更好地表达您的评论建议怎么样？另外,在O符号空间中将二次和三次时间复杂度等同为等于你是完全错误的.有关列表,请参阅https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities. (2认同)
@djechlin Nuzzolilo是对的.**是O(n ^ 2)和O(n ^ 3)之间的差异.系数在big-O表示法中无关紧要,但是权力确实如此.不要混淆系数和常数. (2认同)

Answer 3

您将获得完全n*n/2循环迭代(或者(n*n-1)/2如果n是奇数).在大O符号中我们有,O((n*n-1)/2) = O(n*n/2) = O(n*n)因为常数因素"不计算".

Answer 4

你的算法相当于

while (i += 2 < n*n) 
  ...

哪个是O(n^2/2)相同的,O(n^2)因为大O复杂度不关心常数.