База логарифмов в алгоритмах временной сложности

Какова база логарифма для всех алгоритмов временной сложности? Является ли это базой 10 или базой?

Когда мы говорим, что средняя сложность сортировки равна O (n log n). Является ли основание log n 10 или e?

Ответ 1

В "Информатике" часто используется база 2. Это связано с тем, что многие алгоритмы разделения и покорения, которые проявляют такую сложность, делят проблему на две части на каждом этапе.

Бинарный поиск является классическим примером. На каждом шаге мы делим массив на два и только рекурсивно выполняем поиск в одной из половин, пока не достигнем базового случая подмассива одного элемента (или нулевых элементов). При делении массива длины n на два, общее количество делений до достижения массива из одного элемента log2(n).

Это часто упрощается, потому что логарифмы разных баз фактически эквивалентны при обсуждении анализа алгоритмов.

Ответ 2

В анализе сложности Big-O на самом деле не имеет значения, что такое база логарифмов. (они асимптотически одинаковы, т.е. отличаются только постоянным множителем):

O(log2 N) = O(log10 N) = O(loge N)

В большинстве случаев, когда математики говорят о журналах, они неявно означают основание e. Ученые-компьютеры будут склоняться к основанию 2, но на самом деле это не имеет значения.

Ответ 3

В терминах Big-O основание не имеет значения, поскольку изменение базовой формулы подразумевает, что это только постоянная разность факторов.

Однако иногда полезно подсчитать примерно, сколько операций выполняет алгоритм. В этом случае в большинстве случаев он основывается на 2 из-за природы большинства алгоритмов разделения и покорения.

Ответ 4

Есть некоторые объяснения в этот сайт

В принципе, логарифмы от основания 10 или основания 2 или основания e могут быть заменены (преобразованы) на любое другое основание с добавлением константы. Таким образом, это не имеет значения для базы для журнала.

Главное отметить, что log2N медленно растет. Удвоение N имеет относительно небольшой эффект. Логарифмические кривые хорошо сглаживаются. источник

Ответ 5

Он варьируется в зависимости от проблемы и по большей части не имеет значения. Однако во многих случаях это база 2, например двоичный поиск - log (base 2) n. Вы можете прочитать об этом более подробно здесь.