嵌套循环的时间和 Space 复杂度

Question

请考虑以下算法-

for( j = 1; j < n ; j = j * 3)
{
    for( k = 1 ; k <= n ; k = k + 2 )
    {
      r = i + j + k ;

    System.out.println(r);
    }
}

为此找到的时间和 space 复杂度如何？

Answer 1

外层循环有log₃ n次迭代，内层循环有n / 2次迭代（2是常数，可以忽略），因此时间复杂度为O(N log N).

space 复杂度为 O(1)，因为此处没有针对 N 创建 arrays/lists。