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