Вычисление большой записи O: O (n ^ 4) для 2 вложенных циклов и O (log n) без рекурсии - PullRequest
Новая
       81

Вычисление большой записи O: O (n ^ 4) для 2 вложенных циклов и O (log n) без рекурсии

0 голосов
/ 24 февраля 2019

Прошло много времени с тех пор, как я выполнил некоторые упражнения по приближению сложности во время выполнения, и я пытался обернуть голову вокруг следующих примеров, которые можно найти в Интернете (комментарии мои) :

Пример 1: 

for ( int i = 1 ; i <= n ; i++) { //n
  for ( int j = 1; j <= i*i ; j++) { // 1+2^2+3^2+...+n^2
    if ( j % i == 0) {
      for ( int k = 0 ; k < j ; k++ ){ // 1+2^2+3^2+...+n^2
        sum++;
       }
      }
     }
    }

В листе решения говорится, что это O (n ^ 4), но я его не вижу.Я уверен, что что-то упустил, потому что в своих комментариях я подсчитал, что в худшем случае это O (n ^ 5).

Пример 2: 

i = 1 ;
L2 = -1;
while ( i <= n ) {
  i = i*2 ; // 2 + 2^2 + 2^3+ ...+ 2^n
  L2++;
}

Упомянутое решение - O (log n).Я полагал, что в худшем случае я получу что-то вроде 2 ^ n <= n, таким образом, n <= log n.Здесь было более интуитивно понятно применить типичное определение функции верхней границы (т.е. f (n) <= O (g (x))) </p>

Мне в основном интересно, что я пропустил, и какие шаги / рекомендацииМне нужно было найти правильную сложность больших О для обоих случаев (особенно 1-й пример).Я прошу прощения за любые неясные детали, и я рад добавить больше разъяснений.Заранее спасибо, и я ценю любые идеи!

1 Ответ

0 голосов
/ 24 февраля 2019

Пример 1 - O(n^5), потому что big-O - это верхняя граница.Это также Theta(n^4), потому что оператор if запускает самый внутренний цикл только каждые i итераций, поэтому время выполнения равно Theta(n sum_{i=1}^n (i*i * 1/i * i*i)) = Theta(n^4).

Пример 2 равен O(log n).В j-й итерации i равно 2^j, а пороговое значение для 2^j > n равно j > lg n.

...