проверка Big-O времени выполнения алгоритма

Question

Я пытаюсь научиться правильно доказывать Большой О.

что я пытаюсь сделать, это найти C и N0 для данной функции.

определение, данное для Big-O:

Пусть f (n) и g (n) - функции, отображающие неотрицательные целые числа в действительные числа.Мы говорим, что f (n) есть O (g (n)), если существует действительная постоянная c> 0 и целочисленная постоянная n0 ≥ 1, такая что для всех n ≥ n0 f (n) ≤ cg (n).

Учитывая полином (n + 1) ^ 5, мне нужно показать, что он имеет время выполнения O (n ^ 5).

мой вопрос: как мне найти такойc и N0 из приведенного выше определения, и как мне продолжить мою алгебру, чтобы увидеть, работает ли она n ^ 5?

До сих пор, пробуя индукцию, я имею,

(n +1) ^ 5 = n ^ 5 + 5n ^ 4 + n ^ 3 + 10n ^ 2 + 5n ^ 1 + n ^ 0

найти элемент n + 1, так что

n ^ 5 + 5n ^ 4 + n ^ 3 + 10n ^ 2 + 5n ^ 1 + n ^ 0 <= n ^ 5 + 5n ^ 5 + n ^ 5 + 10n ^ 5 + 5n ^ 5 + n ^5 </p>

n ^ 5 + 5n ^ 4 + 10n ^ 2 + 5n + 1 <= 22n ^ 5 </p>

Answer 1

Требуется постоянная c такая, что (n + 1) ⁵ ≤ cn ⁵ .Для этого вам не нужна индукция, только немного алгебры, и получается, что вы на самом деле уже нашли такой c , но пропустили n ₀ в процессе.Итак, начнем с самого начала.

Обратите внимание, что c не обязательно должен быть жестким, он может быть намного больше, чем необходимо, и все равно будет доказывать сложность времени.Мы будем использовать это в наших интересах.

Сначала мы можем развить левую сторону, как вы.

(n + 1) ⁵ =n ⁵ + 5n ⁴ + 10n ³ + 10 n ² + 5n + 1

Для n ≥ 1 имеем n, n ² , n ³ , n ⁴ ≤ n ⁵ , таким образом.

(n + 1) ⁵ ≤ (1 + 5 + 10+ 10 + 5 + 1) n ⁵ = 22n ⁵

И вот вы получили c такой, что (n + 1) ⁵ ≤ cn ⁵ .Это c равно 22 * ​​1076 *.

И так как мы заявили выше, что это верно, если n ≥ 1 , то у нас есть n ₀ = 1 .

Обобщение

Это обобщает для любой степени.В общем случае, учитывая полином f (n) = (n + a) ^b , тогда вы знаете, что существует число c , которое получается путем суммирования всехкоэффициенты многочлена после развития.Оказывается, точное значение c не имеет значения, поэтому вам не нужно его вычислять, все, что имеет значение, это то, что мы доказали его существование и, таким образом, (n + a) ^b - O (n ^b ) .