为什么O（n ^ 2）这个algorithm的大O复杂性？

我知道这个algorithm的大O复杂度是O(n^2) ，但我不明白为什么。

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

即使我们在开始时设置j = n * n ，我们在每次迭代期间递增i和递减j，所以迭代的结果数量是不是应该比n*nless很多？

在每次迭代中，你增加i和递减j ，这相当于只增加了2。因此，总的迭代次数是n ^ 2/2，仍然是O（n ^ 2）。

大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) 。

你将有n*n/2循环迭代（如果n是奇数，则为(n*n-1)/2 ）。在大O符号中，由于常数因子“不计数”，所以O((n*n-1)/2) = O(n*n/2) = O(n*n) 。

你的algorithm等同于

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

即O(n^2/2)与O(n^2)相同，因为O的复杂度并不关心常量。

设m是所采用的迭代次数。然后，

i + m = n ^ 2 – m

这使，

m =（n ^ 2-i）/ 2

在大O符号中，这意味着O（n ^ 2）的复杂性。

是的，这个algorithm是O（n ^ 2）。

为了计算复杂性，我们有一个表格的复杂性：

O（1）O（log n）O（n）O（n log n）
O（n²）O（n ^ a）O（a ^ n）O（n！）

每行代表一组algorithm。 O（1）中的一组algorithm也在O（n）和O（n ^ 2）等中，但不是相反的。所以，你的algorithm实现n * n / 2句子。

O（n）<O（nlogn）<O（n * n / 2）<O（n 2）

因此，包含algorithm复杂度的一组algorithm是O（n2），因为O（n）和O（nlogn）较小。

例如：对于n = 100，和= 5000. => 100O（n）<200O（n·logn）<5000（n * n / 2）<10000（n ^ 2）

我很抱歉我的英语。

即使我们在开始时设置j = n * n，我们在每次迭代期间递增i和递减j，所以迭代的结果数量是不是应该比n * nless很多？

是! 这就是为什么它是O（n ^ 2）。按照相同的逻辑，它比n * n * n 要小很多，这使得它成为O（n ^ 3）。它甚至是O（6 ^ n），通过类似的逻辑。

大O给你关于上限的信息。

我相信你想问为什么复杂性是theta（n）或者omega（n），但是如果你只是想明白什么是big-O，那么你真的需要明白它首先给出函数的上界，最重要的。