Когда вы умножаете на среднее значение Big O вложенного l oop? - PullRequest
Новая
       5

Когда вы умножаете на среднее значение Big O вложенного l oop?

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

Когда мы умножаем Большой O внешнего l oop на средний Большой O внутреннего l oop? 

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

В этом вопросе внешний l oop равен O (журнал N). Поскольку внутренний l oop выполняется некоторое количество раз на основе 'i', берется среднее значение Big O. Это приводит к суммированию n + n / 2 + n / 4 + ... = 2n, которое затем делится для получения среднего значения: O (2n / log n).

Следовательно, O (log n) * O (2n / log n) = O (n).

Но тогда почему бы нам не взять среднее значение для этого вопроса? 

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

  }
}
Answer: O(n^3)

Внешнее l oop является O (n). Внутренний l oop есть O (n ^ 2). Но почему?

Разве внутренний l oop не выполняется на основе значения 'i' во внешнем l oop? Так почему бы усредненным не принять, как вопрос выше? - что-то вроде O (n ^ 2 / n) для внутреннего l oop.

1 Ответ

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

Сложность алгоритма определяется путем подсчета количества операций, которые он выполняет при выполнении. Для al oop, который повторяется k раз, где m означает среднее количество операций на каждой итерации, общее количество выполненных операций составляет всегда total = k * m, просто потому, что среднее значение определено как m = total / k.

. Это также имеет смысл делать это в большой записи O: если al oop повторяет O(k) раз и выполняет среднее из O(m) операций на каждой итерации общее число операций составляет O(k * m).

Проблема в том, что во втором примере вы неправильно вычисляете среднее значение. Когда вы говорите «Внутренний l oop есть O (n ^ 2)» , , это уже среднее значение ; Вы рассматриваете количество итераций внутренней l oop для одной итерации внешней l oop. Общее число итераций равно O(n^3), а число внешних итераций l oop равно n, поэтому среднее значение равно O(n^3 / n) = O(n^2), как и ожидалось.

Более естественно сделать это вычисление наоборот: после наблюдения, что среднее значение равно O(n^2), а внешнее значение l oop повторяется O(n) раз, итоговое значение составляет O(n^2 * n) = O(n^3).

...