Большой O вложенного L oop (int j = 0; j <i * i; ++ j) - PullRequest
Новая
       9

Большой O вложенного L oop (int j = 0; j <i * i; ++ j)

1 голос
/ 23 января 2020

Вопрос 1 

for (i = 0; i < n; i++) {
  for (j = 0; j < i * i ; j++){

  }
}
Answer: O(n^3)

На первый взгляд, O (n ^ 3) имело смысл для меня, но я помню предыдущую проблему, которую я сделал:

Вопрос 2 

for (int i = n; i > 0; i /= 2) {
   for (int j = 0; j < i; j++) {
     //statement
   }
}
Answer: O(n)

Для Вопроса 2 внешний l oop равен O (log n), а внутренний l oop равен O (2n / log n), что приводит к На). Внутренний l oop равен O (2n / log n), потому что - см. Объяснение здесь: Большой O вложенного L oop (int j = 0; j

Почему мы не делаем Вопрос 1, как Вопрос 2, поскольку в Вопросе 1 j также зависит от i, что означает, что мы действительно должны брать среднее число повторений, которое произойдет во внутренней l oop (как мы делаем в вопросе 2).

Мой ответ будет таким: O (n) для внешнего l oop и O (n ^ 2 / n) для внутреннего l oop, что приводит к O (n ^ 2) для вопроса 1 .

Ответы [ 3 ]

2 голосов
/ 23 января 2020

Ваш ответ неверный. Код: Θ(n³).

. Обратите внимание, что внутренний l oop делает i² шагов, что не более n², но для половины внешних итераций l oop это как минимум (n/2)² = n²/4.

Следовательно, количество полных внутренних итераций не более n * n² = n³, но не менее n/2 * n²/4 = n³/8.

Ваше мнение неверно в том, что внутреннее l oop занимает в среднем пропорционально n² много итераций, а не n² / n.

1 голос
/ 23 января 2020

То, что делает ваш внутренний for l oop, в сочетании с внешним for l oop вычисляет сумму i^2. Если вы пишете это, вы добавляете следующие термины: 

1 + 4 + 9 + 16 + ...

Результат этого равен (2n^3+3n^2+n)/6. Если вы хотите вычислить среднее число итераций внутреннего for l oop, вы делите его на n, так как это число итераций внешнего for l oop. Таким образом, вы получите (2n^2+3n+1)/6, с точки зрения обозначения Big O это будет O(n^2). И это не дает тебе ... ничего. Вы не получили никакой новой информации, поскольку вы уже знали, что внутренняя сложность for l oop равна O(n^2). * O(n^2) выполнение n раз дает вам O(n^3) общей сложности, которую вы уже знали ...

Итак, вы можете вычислить среднее число итераций внутреннего for l oop, но вы не получите никакой новой информации. Количество шагов итерации не уменьшилось, как в предыдущем вопросе (материал i /= 2).

0 голосов
/ 23 января 2020 
void fun(int n, int k) 
{ 
    for (int i=1; i<=n; i++) 
    { 
      int p = pow(i, k);  
      for (int j=1; j<=p; j++) 
      { 
          // Some O(1) work 
      } 
    } 
}

Временная сложность вышеуказанной функции может быть записана как 1k + 2k + 3k +… n1k.

В вашем случае k = 2 

Sum = 12 + 22 + 32 + ... n12.
    = n(n+1)(2n+1)/6
    = n3/3 + n2/2 + n/6
...