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

标签： javaruntime

Answer 1

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