Какова временная сложность следующего сегмента кода?

Question

Для нижеприведенного сегмента кода оценивайте сложность времени в примечаниях с большими о-ми.

for (int i=0; i< n; i++) 

for (int j=0; j*j <n;j++) 

for (int k=0; k < n/2;k++) 
    System.out.println (i+j+k); 

Я думаю, что они вложенные петли, но я не уверен на 100%. Из того, что я могу понять, наихудшее время для первого цикла - O (n), второе - O (sqrt (n)), а третье - O (log n). Это верно? И я бы просто умножал эти значения, чтобы получить временную сложность для всего цикла?

Answer 1

Я думаю, что O (n * (n^(1/2)) * (n/2)). Но я не уверен.

Answer 2

for (int i=0; i< n; i++) {    // O(n) 
    for (int j=0; j*j <n;j++) {   // O(n^0.5) 
     for (int k=0; k < n/2;k++) {  // O(0.5*n) 
      System.out.println (i+j+k); // O(1) 
}}} 

То же утверждение сферы применения добавляется, вложенные операторы умножаются

O((n)*(n^0.5)*(0.5*n)*(1)) = O(0.5*(n^2)*(n^0.5)) = O(0.5n^2.5) = O(n^2.5)

Answer 3

Чтобы расширить на комментарии Криптона, петли следующим образом:

• Петля 1: O (n), как вы упомянули
• Петля 2: O (sqrt (n)) == O (n^(1/2)), как вы упомянули.
• Петля 3: O (n/2), которая, удаляя постоянный коэффициент, равна O (n).

Умножая, петли 1 и 3 вместе представляют собой O (n^2), а три вместе представляют собой O (n^(5/2)) или O (n^(2.5)). Это в некоторой нечетной серой области между квадратичным и полиномиальным временем.

Answer 4

for (int i=0; i< n; i++) ------------------------------------ 
                  | 
    for (int j=0; j*j <n;j++) ----------------------   | 
                |   | O(n) 
     for (int k=0; k < n/2;k++) -------  |   | 
              |O(n/2) |O(n^1/2) | 
      System.out.println (i+j+k); ---  |   | 
                |   | 
           ----------------------   |   
                  | 
          ------------------------------------ 

Следовательно, во время выполнения

O(n)*O(n^1/2)*O(n/2) = O(n^(5/2)) 

Answer 5

Loop 1 скорость изменения линейно зависит от п -> О (п) - Линейный

Цикл 2 Скорость изменения зависит от квадрата корня п -> о (п^0,5) - Дробное питание

Цикл 3 скорость изменения линейно зависит от п/2, но 1/2 константа может быть удалена -> о (п/2) - Линейный

Таким образом, общая сложность будет O (N) * O (п^0,5) * O (п) = О (п^2,5)

Проверить это для получения дополнительной информации: http://www.brpreiss.com/books/opus5/html/page72.html