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

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})

第三次循环：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( ¹ ⁄<sub>2N) ->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( ¹ ⁄<sub>2N) ->O(N)

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