Показать 2 ^ n это O (n!)

Question

Я изо всех сил пытаюсь понять, почему они равны. Помощь будет оценена. Я пытался сказать, как 2 ^ n подразумевает удвоение n раз , но я не уверен, насколько это похоже на факториал.

Answer 1

Чтобы доказать, что 2 ⁿ равно O (n!) , вам нужно показать, что 2 ⁿ ≤ M · n! , для некоторой константы M и всех значений n ≥ C, где C также некоторая постоянная.

Итак, давайте выберем M = 2 и C = 1 .

Для n = C, мы видим, что 2 ⁿ = 2 и M · n! = 2, поэтому действительно в этом базовом случае 2 ⁿ ≤ M · n! истинно.

Если предположить, что оно верно для некоторых n (≥ C), то также верно для n + 1 ? Да, потому что если 2 ⁿ ≤ M · n! , то также 2 ^{n + 1} ≤ M · (n + 1)!

Левая сторона умножается на 2, в то время как правая сторона умножается на как минимум 2.

Таким образом, это индуктивно доказывает, что 2 ⁿ ≤ M · n! для всех n ≥ C, для выбранных значений для M и C. В результате 2 ⁿ равно O (n!) .

Answer 2

2 ^ n и n! не "равны". В формальной математике существует важное различие, которое часто упускается из виду, когда люди говорят, что «функция a есть O of b». Это просто означает, что асимптотически b является верхней границей a. Это означает, что технически n - это O (n!), 1 - это O (n!) И т. Д. c. Это тривиальные примеры. Точно так же n! не O (2 ^ n) .

Неформально, особенно в информатике, обозначение больших O часто можно использовать несколько иначе, чтобы описать асимптотику c с жесткой границей при использовании больших Тета-нотация может быть более уместной в конкретном контексте.

wikipedia