Какой номер опущен в журнале O (log n)?

Question

В O (log n), какое основание, "2" или "10" опущено?Способ временной сложности log n основывается на делении последовательности, поэтому его должно быть 2. Обычно база 10 опускается в log.

Answer 1

Эта запись показывает, как время выполнения алгоритма увеличивается относительно размера N. Не имеет значения, на какую базу он ссылается.Точно так же, как это не имеет значения, если его O (n) или O (k * n) (будучи ka реальной константой).

Уточнение:

Журнал в любой заданной базе Xможно записать следующим образом:

log _x (n) = ^{log ₁₀ (n)} ⁄ _{log 10 (x)}

Пусть k = log ₁₀ (x), поэтому имеем:

log _x (n) = (1 ⁄ k) × log ₁₀ (n)

, что также является функцией log сложности (n)

Мое предложение визуализировать этоСвойство проще состоит в том, чтобы думать, что умножение функции на константу заставляет ее график растягиваться (или уменьшаться) по вертикали, что не меняет форму самой кривой.И форма этого обозначения.

Из Википедии:

Аналогично, журналы с различными константами оснований эквивалентны.