这个 for 循环的运行时复杂度是多少?

Question

我试图找出这个算法的运行时复杂性。

public static void main(String[] args) throws InterruptedException{
for (int N=100; N<=1000000; N=N*5) {  
long start = System.currentTimeMillis();
for (int i = 1; i <= N; i++) {     
for (int j = 1; j <= Math.pow(N,1.5); j++) {
i = i*2;
j = j*2;
Thread.sleep(10); 
} 
}
long stop = System.currentTimeMillis();
long elapsed = (long)(stop - start);
System.out.println();
System.out.println("For N=" + N + " RT in msec: "+elapsed); 
}
}

第一个 for 循环：

for (int N=100; N<=1000000; N=N*5) // runs n/5 times, so O(n). 

第一个内循环：

for (int i = 1; i <= N; i++) // runs n times. 

第二个内循环：

for (int j = 1; j <= Math.pow(N,1.5); j++) { // we can consider Math.pow O(1)
i = i*2;
j = j*2;
Thread.sleep(10); 
} 

因此，通过乘以所有 O(n( * O(n( * O(1( = O(n^2( 我的答案正确吗？我对此有点困惑。 将不胜感激对此的任何澄清。谢谢

Answer 1

第一个循环实际上是O(k)哪个5^k = N。因此，k = log_5(N). 第一个内部循环为真(以O(n)为单位(。 而第二个内循环j是每次都是2的时间。因此，O(h)2^h = N^1.5.因此，h = 1.5 log(N).

总之，算法是O(log_5(N) * N * log(N)) = O(N log^2(N)).