Big O - Не понимаете сложность времени для этих алгоритмов?

Question

Я изучаю, как делать временную сложность в школе, и профессор загрузил несколько примеров. Для первого примера ниже ответ должен быть O (n^3), но я не понимаю, как это сделать.

public static int fragment1 (int n) 
{ 
    int sum = 0; 
    for (int i = 1; i <= n*n; i++) 
     for (int j = 0; j*j < i; j++) sum++; 
    return sum; 
} // end fragment1 

Когда я пытаю проблему, я смотрю на первый цикл и увидеть, что он работает п^2 раза, то внутренний цикл также п^2. При добавлении я получаю O (n^4).

public static int fragment5 (int n) 
{ 
    int sum = 0; 
    for(int i=0; i < n*n*n; i++) 
    { 
     if(i%(n*n) == 0) { 
      for(int j=i*i; j > 0; j--) 
       sum++; 
     } // if 
     else 
     { 
      for(int k=0; k < i: k++) 
       sum++; 
     } // else 
    } // outer loop 
} 

Для решения проблемы выше должен быть O (n^7). Когда я попытался, я получил: сначала для циклов пробегает n^3 раза, внутренний для цикла n^3 * n^3 = n^6, а цикл for внутри оператора else я получаю n, а мой окончательный ответ - O (n^10). Может ли кто-нибудь дать мне советы по вышеуказанной проблеме? Я чувствую себя невежественным, когда дело доходит до этого, и до сих пор я получал другие проблемы.

Answer 1

Одним из основных допущений при вычислении BigO является . Не преобладающие условия.

Используя первый пример,

• по внешнему контуру имеет порядок O (N^2)
• Внутренний контур имеет порядок O (N^3)
  • Внутренний цикл независимо друг от друга работает в течение 'п' раз, но потому, что он вложен, он будет работать в 'п * (п^2) '

Итак, BigO имеет вид O ((n^2) + (n^3)), которого было бы достаточно для O (n^3).

Вы можете попробовать использовать ту же технику для второй проблемы.
Если вы все еще есть некоторая путаница, посмотреть на следующем видео: Big O Notation