Помогите рассчитать Big O

Question

Я пытаюсь получить правильный Big-O следующего фрагмента кода:

s = 0
for x in seq:
  for y in seq:
    s += x*y
  for z in seq:
    for w in seq:
      s += x-w

Согласно книге, из которой я получил этот пример (Алгоритмы Python), они объясняют это так:

Z-цикл выполняется для линейного числа итераций и содержит линейный цикл, поэтому общая сложность здесь квадратичная, или Θ (n ² ).Y-петля явно Θ (n).Это означает, что блок кода внутри x-цикла равен Θ (n + n ² ).Весь этот блок выполняется для каждого цикла цикла x, который выполняется n раз.Мы используем наше правило умножения и получаем Θ (n (n + n ² )) = Θ (n ² + n ³ ) = Θ (n ³ ), то есть куб.

Чего я не понимаю, так это: как O (n (n + n ² )) может стать O (п ³ )?Математика верна?

Answer 1

Математика здесь делается следующим образом.Когда вы говорите O (n (n + n ² )), это эквивалентно выражению O (n ² + n ³ ), просто распределяя n по всемупроизведение.

Причина, по которой O (n ² + n ³ ) = O (n ³ ) следует из формального определенияобозначение big-O, которое выглядит следующим образом:

Функция f (n) = O (g (n)), если существуют константы n ₀ и c такие, что длялюбой n ≥ n ₀ , | f (n) |≤ c | g (n) |.

Неофициально это говорит о том, что, когда n становится произвольно большим, f (n) сверху ограничивается постоянным кратным g (n).

Чтобы формально доказать, что n ² + n ³ есть O (n ³ ), рассмотрим любое n ≥ 1. Тогда мы получим это

n ² + n ³ ≤ n ³ + n ³ = 2n ³

Итак, имеем n ² + n ³ = O (n ³ ), с n ₀ = 1 и c = 2. Следовательно, имеем, что

O (n (n + n ² )) = O (n ² + n ³ ) = O (n ³ ).

Чтобы быть по-настоящему формальным, нам нужно показать, что если f (n)= O (g (n)) и g (n) = O (h (n)), тогда f (n) = O (h (n)).Давайте пройдемся по доказательству этого.Если f (n) = O (g (n)), существуют константы n ₀ и c такие, что для n ≥ n ₀ , | f (n) |≤ c | g (n) |.Аналогично, поскольку g (n) = O (h (n)), существуют константы n ' ₀ , c', такие что для n ≥ n ' ₀ , g (n)≤ c '| h (n) |.Таким образом, это означает, что для любого n ≥ max (c, c ') мы имеем, что

| f (n) |≤ c | g (n) |≤ c | c'h (n) |= cxc '| h (n) |

И так f (n) = O (h (n)).

Чтобы быть немного более точным - в случаеПо описанному здесь алгоритму авторы говорят, что время выполнения равно is (n ³ ), что является более сильным результатом, чем утверждение, что время выполнения равно O (n ³ ).Θ нотация обозначает жесткую асимптотическую границу, означающую, что время выполнения растет с той же скоростью, что и n ³ , а не только потому, что оно ограничено сверху некоторым кратным n ³ .Чтобы доказать это, вам также необходимо показать, что n ³ равно O (n ² + n ³ ).Я оставлю это в качестве упражнения для читателя.: -)

В более общем случае, если у вас есть любой полином порядка k, этот полином равен O (n ^k ), используя аналогичный аргумент.Чтобы увидеть это, пусть P (n) = ∑ _{i = 0} ^k (a _i n ⁱ ).Тогда для любого n ≥ 1 имеем

∑ _{i = 0} ^k (a _i n ⁱ ) ≤ ∑ _{i = 0} ^k (a _i n ^k ) = (∑ _{i = 0} ^k (a _i )) n ^k

, поэтому P (n) = O (n ^k ).

Надеюсь, это поможет!

Answer 2

O(n(n+n^2)) = O(n^2 + n^3)

Поскольку термин n^3 доминирует над термином n^2, термин n^2 пренебрежимо мал и поэтому равен O(n^3).

Answer 3

n (n + n ² ) == n ² + n ³

Обозначение Big-O заботится только о доминирующем члене, когда n обращается в бесконечность, поэтому весь алгоритм рассматривается как Θ (n ³ ).

Answer 4

цикл y можно обесценить из-за цикла z (O (n) + O (n ^ 2) -> O (n ^ 2)) Забудьте арифметику. Затем у вас останется три вложенных цикла, которые повторяются по всей длине 'seq', поэтому это O (n ^ 3)