Основание логарифма при оценке сложности алгоритма nlog(n) Привет.
Начал учить алгоритмы, по образованию не IT никак.
Не могу понять. Допустим BigO для Merge Sort - nlog(n)
Какое основание у этого логарифма? Натуральный ln, десятичный lg. Непонятно.
Основание логарифма при оценке сложности алгоритма nlog(n) Привет.
Начал учить алгоритмы, по образованию не IT никак.
Не могу понять. Допустим BigO для Merge Sort - nlog(n)
Какое основание у этого логарифма? Натуральный ln, десятичный lg. Непонятно.
Начал учить алгоритмы, по образованию не IT никак.
Не могу понять. Допустим BigO для Merge Sort - nlog(n)
Какое основание у этого логарифма? Натуральный ln, десятичный lg. Непонятно.
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Привет!
В случае анализа сложности алгоритма, когда говорят о логарифмической сложности O(log(n)), обычно подразумевается логарифм по основанию 2 (lg). Однако, когда говорят о Merge Sort и его сложности O(nlog(n)), тут уже имеют в виду логарифм по основанию 2, но умноженный на n. То есть основание логарифма в данном случае не имеет особого значения, главное, что сложность алгоритма будет линейно-логарифмической.
Если у вас нет конкретного указания, какое основание логарифма следует использовать, можно считать, что имеется в виду логарифм по основанию 2 (lg).