这个嵌套循环的 Big-O 是什么？

Question

int z=1; 
for（int i=0;i*i<n;i++）｛
  z*=3;
  for（int j=0;j<z;j++）{
   // Some code
  }
}

答案是 O(3^n)。这是对的吗？如何计算嵌套循环的时间复杂度？

Answer 1

外循环：i 从 1 到 sqrt(n)；内循环：j,z 上升到 3^(sqrt(n));

"some code" 将运行 1 + 3 + 3^2 + ... + 3^(sqrt(n)) 次

let sum = 1 + 3 + 3^2 + ... + 3^(sqrt(n))
sum - 3*sum = 1 - 3(sqrt(n) + 1)
sum = 1 - 3(sqrt(n) + 1) / (1-3) = 2( 3^(sqrt(n)+1) - 1 )

2( 3^(sqrt(n)+1) - 1 ) << O( 3^sqrt(n) )

O(3^sqrt(n)) 更准确

Answer 2

您可以这样使用 Sigma 表示法解决问题：

What is the Big-O of this nested loop?