@Nodar
Python, Ruby, JavaScript

Основание логарифма при оценке сложности алгоритма nlog(n)

Привет.
Начал учить алгоритмы, по образованию не IT никак.
Не могу понять. Допустим BigO для Merge Sort - nlog(n)
Какое основание у этого логарифма? Натуральный ln, десятичный lg. Непонятно.
  • Вопрос задан
  • 3749 просмотров
Решения вопроса 1
Зависит от того, на сколько частей делится массив, это и будет основанием логарифма.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
@throughtheether
human after all
Одно из свойств этой нотации - отбрасывание констант перед членами, а также младших (менее быстро растущих) членов. Кроме того, log[base=a](N)=log[base=b](N)/log[base=b](a), т.е. при смене основания логарифма эффективно меняется константа перед соответствующим членом, что в целом не учитывается ('подавляется') О-нотацией.
Ответ написан
@Nodar Автор вопроса
Python, Ruby, JavaScript
@WolfdalE
Правильно понимаю: есть список [9,4,3,6,8,1]. Если при сортировке он делится на 2 [9,4,3] и [6,8,1], то основание логарифма 2. Если на 3 [9,4], [3,6], [8,1], то основание - 3?
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы