为什么这个算法的Big-O复杂度是O(n^2)？
Why is the Big-O complexity of this algorithm O(n^2)?
我知道这个算法的大 O 复杂度是 O(n^2)，但我不明白为什么。
int sum = 0;
int i = 1; j = n * n;
while (i++ < j--)
sum++;
虽然我们一开始就设置了j = n * n，但是每次迭代的时候都是自增i自减j，所以迭代的次数不应该比n*n少很多吗？
在每次迭代中，您递增 i 并递减 j，这相当于将 i 递增 2。因此，总迭代次数为 n^2 / 2，并且仍然是 O(n^2).
设 m 为迭代次数。那么，
i+m = n^2 - m
这给出了，
m = (n^2-i)/2
在大 O 表示法中，这意味着复杂度为 O(n^2)。
您将有 n*n/2 个循环迭代（如果 n 为奇数，则为 (n*n-1)/2）。
在大 O 表示法中我们有 O((n*n-1)/2) = O(n*n/2) = O(n*n) 因为常数因子 "don't count".
大 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) 是一样的。
是的，这个算法是O(n^2)。
要计算复杂度，我们有 table 个复杂度：
O(1)
O(log n)
在）
O(n log n)
O(n²)
O(n^a)
O(a^n)
O(n!)
每一行代表一组算法。一组算法在 O(1) 中，也在 O(n) 和 O(n^2) 等中。但不是反过来。所以，你的算法实现了n*n/2句
O(n) < O(nlogn) < O(n*n/2) < O(n²)
因此，包含算法复杂度的算法集为 O(n²)，因为 O(n) 和 O(nlogn) 更小。
例如：
至 n = 100，总和 = 5000。=> 100 O(n) < 200 O(n·logn) < 5000 (n*n/2) < 10000(n^2)
对不起我的英语。
你的算法等同于
while (i += 2 < n*n)
...
与 O(n^2) 相同的 O(n^2/2) 因为大 O 复杂性不关心常量。
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?
是的！这就是为什么它是 O(n^2)。按照同样的逻辑，它比 n * n * n 少 lot，这使得它成为 O(n^3)。根据类似的逻辑，它甚至是 O(6^n)。
big-O 为您提供有关上限的信息。
我相信你想问的是为什么复杂度是 theta(n) 或 omega(n)，但如果你只是想了解 big-O 是什么，你 真的 需要了解它首先给出函数的 上限 。
我知道这个算法的大 O 复杂度是 O(n^2)，但我不明白为什么。
int sum = 0;
int i = 1; j = n * n;
while (i++ < j--)
sum++;
虽然我们一开始就设置了j = n * n，但是每次迭代的时候都是自增i自减j，所以迭代的次数不应该比n*n少很多吗？
在每次迭代中，您递增 i 并递减 j，这相当于将 i 递增 2。因此，总迭代次数为 n^2 / 2，并且仍然是 O(n^2).
设 m 为迭代次数。那么，
i+m = n^2 - m
这给出了，
m = (n^2-i)/2
在大 O 表示法中，这意味着复杂度为 O(n^2)。
您将有 n*n/2 个循环迭代（如果 n 为奇数，则为 (n*n-1)/2）。
在大 O 表示法中我们有 O((n*n-1)/2) = O(n*n/2) = O(n*n) 因为常数因子 "don't count".
大 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) 是一样的。
是的，这个算法是O(n^2)。
要计算复杂度，我们有 table 个复杂度：
O(1)
O(log n)
在）
O(n log n)
O(n²)
O(n^a)
O(a^n)
O(n!)
每一行代表一组算法。一组算法在 O(1) 中，也在 O(n) 和 O(n^2) 等中。但不是反过来。所以，你的算法实现了n*n/2句
O(n) < O(nlogn) < O(n*n/2) < O(n²)
因此，包含算法复杂度的算法集为 O(n²)，因为 O(n) 和 O(nlogn) 更小。
例如： 至 n = 100，总和 = 5000。=> 100 O(n) < 200 O(n·logn) < 5000 (n*n/2) < 10000(n^2)
对不起我的英语。
你的算法等同于
while (i += 2 < n*n)
...
与 O(n^2) 相同的 O(n^2/2) 因为大 O 复杂性不关心常量。
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?
是的！这就是为什么它是 O(n^2)。按照同样的逻辑，它比 n * n * n 少 lot，这使得它成为 O(n^3)。根据类似的逻辑，它甚至是 O(6^n)。
big-O 为您提供有关上限的信息。
我相信你想问的是为什么复杂度是 theta(n) 或 omega(n)，但如果你只是想了解 big-O 是什么，你 真的 需要了解它首先给出函数的 上限 。