Вы правы, что 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 до степени набора функций не имеет смысла в этом контексте, но достаточно распространено для понимания.