确定这些循环的 Big-O 运行时

Question

我正在尝试确定这些循环的 Big-O 运行时。我相信我的答案是正确的，但我想与社区核实一下。

int sum = 0;
for (int i = 1; i <= n*2; i++ )
   sum++;

我的答案是 O(n)

这是因为循环重复 n x 2 次。我们去掉 2，剩下 n。因此 O(n).

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = n; j > 0; j /= 2)
      sum++;

我的答案是 O(n lgn)

外层循环迭代n次。内部循环从 n 向下迭代到 0，但只迭代了一半的项目。结果是 Log base 2 of n。我们删除 2 并保留 log n。内循环 (log n) 乘以外循环 (n)，得到 O(n lgn)。

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = i; j <= n; j += 2)
      sum++;

我的答案是 O(n^2)

这个很简单。内循环和外循环各迭代n次。 n x n = n^2。因此 O(n^2).

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

我的答案是 O(n^3)

我的回答正确吗？如果不是，我该如何更正它们？

Answer 1

只有最后一个错了。应该是 O(n⁴).

您可以这样看：将 n * n 替换为 x。操作次数通常为 O(x*(x+1)/2) = O(x²)。现在将 n * n 替换回 x.

给你额外的挑战。

你说得对：

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = n; j > 0; j /= 2)
      sum++;

是O(n log n)。但是这个呢:

int sum = 0;
for ( int i = 1; i <= n; i++)
   for ( int j = i; j > 0; j /= 2)
      sum++;

我只把j = n改成了j = i。

Determine Big-O runtime for these loops