Big O обозначение для экспоненциальной и логарифмической сложности

Question

Есть много вопросов по поводу больших обозначений O, но я не нашел четкого ответа на этот вопрос.

Мы пишем, что:O (5n) = O (n)а такжеO (3n ^ 2 + n + 2) = O (n ^ 2)

Можем ли мы написать, что:O (2 ^ (2n)) = O (2 ^ n)?

То же самое для логарифмической сложности: O (n log (4n)) = O (n log (n))?

Answer 1

Единственные константы, которые вы можете удалить, являются аддитивными и мультипликативными. Значение O (f ( n )) = O (f ( n ) + C) = O (C & times; f ( n )).

2 ^{2 n} = (2 ⁿ ) ² . Эта 2 константа не может быть проигнорирована, поскольку она является показателем степени. Так же, как O ( n ) и O ( n ² ) являются различными классами сложности, O (2 ^{n )} ) и O (2 ^{2 n} ).

С другой стороны, да, O ( n log 4 n ) = O ( n log n ). Мы можем использовать логарифмическую идентичность, чтобы превратить 4 в мультипликативную константу: O ( n log 4 n ) = O ( n (log n) + log 4)) = O ( n log n + (log 4) n ) = O ( n log n + n ) = O ( n log n ).