Какие константы могут быть проигнорированы в Big O для сложности времени - экспоненциальные случаи? - PullRequest
3 голосов
/ 04 февраля 2020

Очевидным является константа на линейном члене, например, 2n, 4n и 8n - это просто n или O (n).

Но как насчет экспоненциальной постоянной 1.6 ^ n * 1004? * и 2 ^ n . В этом случае константа, по-видимому, оказывает большее влияние на сложность времени.

Также не существует действительно удобного способа написать все для экспоненциальной сложности времени.

O (K ^ n) возможно.

В этом шпаргалке они, кажется, используют O (2 ^ n) , означает ли это, что все экспоненциальные сложности должен быть написан таким образом?

Вероятно, нет.

Ответы [ 2 ]

2 голосов
/ 04 февраля 2020

Вы правы, что 2n, 4n и 8n - это просто O (n), и вы также правы, что O (1.6 n ) - это не то же самое, что O (2 ) п ). Чтобы понять почему, нам нужно обратиться к определению обозначения больших O.

Обозначение O (...) означает набор функций. Функция f (n) находится в множестве O (g (n)) тогда и только тогда, когда для некоторых констант c и n 0 мы имеем f (n) ≤ c * g (n) всякий раз, когда n ≥ n 0 . Учитывая это определение:

  • Функция f (n) = 8n находится в наборе O (n), потому что если мы выберем c = 8 и n 0 = 1, у нас есть 8n ≤ 8 * n для всех n ≥ 1.
  • Функция f (n) = 2 n равна , а не в установите O (1,6 n ), потому что какой бы c и n 0 мы выбрали, 2 n > c * 1,6 n для некоторого достаточно большого n. Мы можем выбрать n> log 2 c + n 0 log 2 1.6 для конкретного контрпример.
  • Обратите внимание, что f ( n) = 1,6 n равно в наборе O (2 n ), поскольку 1,6 n ≤ 1 * 2 n для всех n ≥ 1.

Для "всеобъемлющего" способа написания экспоненциальной сложности вы можете написать 2 O (n) . Это включает в себя экспоненциальные функции с произвольными основаниями, например, функцию f (n) = 16 n , поскольку это равно 2 4n , а 4n находится в наборе O (n). Это злоупотребление нотацией , поскольку повышение числа 2 до степени набора функций не имеет смысла в этом контексте, но достаточно распространено для понимания.

1 голос
/ 27 февраля 2020

Это правильно. Шпаргалка, которую вы связали с здесь , не может показать все различные сложности, поэтому она выбирает наиболее распространенные из них.

Проще говоря, если у вас есть функция, растущая на 3 ^ n. Это не может быть классифицировано как 2 ^ n, потому что оно нарушит определение Big O.

Теория математики, которая описывает Big O, просто говорит, что она никогда не может быть больше. А также игнорировать линейные константы роста.

f(n) ≤ c * g(n) whenever n ≥ n0
...