大哦分析

Question

代码 1：

我认为这段代码是 O(n^3)，因为外循环运行 n^2 次而内循环运行 n 次。根据我的教授，这段代码不是 O(n^3)。有人可以解释为什么吗？我真的很困惑。

i, j, sum = 1, 1, 0

while i < n**3:
  while j < n:
     sum = sum + i
     j += 1
  i = i + n

代码 2：

我认为这段代码是 O(n)。有人可以确认一下吗？

i, j, sum = 0, 0, 0

while i ** 2 < n:
  while j ** 2 < n:
     sum += i*j
     j += 2
  i += 4

Answer 1

i, j, sum = 1, 1, 0

while i < n**3:
  while j < n:
     sum = sum + i
     j += 1
  i = i + n

请注意，内循环仅在外循环的第一遍期间执行，因为 j 不会像在 for 循环中那样重新初始化。很明显，内循环的运行时间恰好是 n。另一方面，外循环执行了 n^2 次。为什么？观察 i 的变化：首先是 1，然后是 n+1，然后是 2n+1，...，最后是 n^2*n+1，所以 i递增 n^2 次。因此，总运行时间为n + n^2，即O(n^2).

i, j, sum = 0, 0, 0

while i ** 2 < n:
  while j ** 2 < n:
     sum += i*j
     j += 2
  i += 4

与第一种情况类似的分析，附加说明条件 while i ** 2 < n 等同于 while i < sqrt(n)。内循环仅在外循环的第一遍期间执行，其运行时间为 sqrt(n) / 2，因为 j 递增 2（而不是递增 1）。外循环运行 sqrt(n) / 4 次，所以总运行时间为 sqrt(n) / 2 + sqrt(n) / 4，即 O(sqrt(n)).

大哦分析

Big oh Analysis

big-o

python-3.x