Основание логарифма при оценке сложности алгоритма nlog(n) Привет.
Начал учить алгоритмы, по образованию не IT никак.
Не могу понять. Допустим BigO для Merge Sort - nlog(n)
Какое основание у этого логарифма? Натуральный ln, десятичный lg. Непонятно.

Предыдущий
вопрос Следующий
вопрос

Привет!

В случае анализа сложности алгоритма, когда говорят о логарифмической сложности O(log(n)), обычно подразумевается логарифм по основанию 2 (lg). Однако, когда говорят о Merge Sort и его сложности O(nlog(n)), тут уже имеют в виду логарифм по основанию 2, но умноженный на n. То есть основание логарифма в данном случае не имеет особого значения, главное, что сложность алгоритма будет линейно-логарифмической.

Если у вас нет конкретного указания, какое основание логарифма следует использовать, можно считать, что имеется в виду логарифм по основанию 2 (lg).