java - 确定函数:的运行时间

Question

public static void p2(int N) { 
  for (int i = 0; i < N; i += 1) { 
    for (int j = 1; j < N; j = j * 2) {  
        System.out.println("hi !"); 
    } 
  } 
}

你能帮我确定这个函数的运行时间吗？

我尝试为 N 的不同输入找到一些模式。我计算了最多 5 个输入的成本(println 用于此目的):

N:0、1、2、3、4、5

C(N):0、0、2、6、8、15

其中 C(N) 是成本函数。

但是，我不知道下一步该怎么做!答案是 θ(N log(N))

Answer 1

内部循环将执行lg n次。您可以通过查看 N 除以 2 多少次得到 1 来理解这一点？ (即内部循环将执行多少次？)答案是 lg n。外层循环将运行N次。因此，对于 i 的每次迭代，内部循环将运行 lg n 次。这意味着嵌套循环将恰好运行 n(lgn) 次，这就是该问题的时间复杂度。