多个嵌套循环的时间复杂度

Question

下面代码的复杂度是多少：由于增量不是1，条件不直接，复杂度如何计算？

for(int h =0; h<n;h+=2)
    {
       for (int j =1; j<=n*n; j*=3)
       {
          for (int k =2; k+k <=n;++k)
          { 
          } 
       } 
    }

Answer 1

第一个循环：n次，不断跳跃（+2）。因此 n/2 次是 O(n)

第二个循环：n^2 次，几何跳跃 (*3) 因此 \log_{3}{n^2} = O(\log{n})

第3次循环：n/2次，也就是n/2次

循环是嵌套的，所以你得到了 O\(n*log{n}*\)=O\(n^{2}log{n}\)

Answer 2

有 3 个嵌套循环。让我们分析它们中的每一个（请记住，我们不关心任何常量，无论它们有多大）：

for(int h=0; h<n; h+=2) - O(¹⁄₂N) -> O(N)

for (int j=1; j<=n*n; j*=3) - O(log₃N²) -> O(logN2)

for (int k=2; k+k<=n; ++k)- O(¹⁄₂N) -> O(N)

因为所有循环都是嵌套的 O(N * logN² * N) -> O(N2*logN2)

多个嵌套循环的时间复杂度

Time Complexity of multiple nested loops

big-o

time-complexity

nested-for-loop