Какова сложность во время выполнения этого цикла for? - PullRequest
Новая
       39

Какова сложность во время выполнения этого цикла for?

0 голосов
/ 07 октября 2018

Я пытаюсь выяснить сложность этого алгоритма во время выполнения.

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) Мой ответ правильный?Я немного запутался в этом.Буду признателен за любые разъяснения по этому вопросу.Спасибо

1 Ответ

0 голосов
/ 07 октября 2018

Первый цикл на самом деле O(k), что 5^k = N.Следовательно, k = log_5(N).Первый внутренний цикл имеет значение true (в 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)).

...