什么是 Big-O 和确切的运行时间

Question

def alg 3(n)
  x = 0
  i = 1
  while i < n:
     for j in range(0, n**3,n*3): 
        x += 1
     i *= 3 
  return x 

我不太了解这段代码的大 O 和确切的运行时间。我首先认为 Big-O 是 O(n^3) * logn 因为 n**3 但 n * 3 让我感到困惑。有人可以解释这个问题吗？谢谢

Answer 1

为了计算复杂度，我们必须将问题分解为两个子问题：

1. 内因：这个的复杂度是n³/3n ~ O(n²)
2. 外面的 while: 我需要多少步才能达到 n:
   1. 第一步i=1
   2. 第二步i=3
   3. 第三步i=3*3=9
   4. 第 k 步 i = 3^k

因此第二个子问题的解是log3(k) ~ O(log(k))

最终的复杂度是：第一个子问题的复杂度乘以第二个子问题的复杂度 --> O(n²log(n))