Большая путаница O: log2 (N) против log3 (N)

Большой O не имеет дело с постоянными факторами, и разница между Log_x(n) и Log_y(n) является постоянным фактором.

Другими словами, основание логарифма просто изменяет наклон линии/кривой на графике. Big-O не имеет отношения к наклону кривой на графике, а только к форме кривой. Если вы можете заставить одну кривую совпадать с другой, сдвигая ее наклон вверх или вниз, то, насколько это важно для нотации Big-O, это одна и та же функция и одна и та же кривая.

Чтобы попытаться представить это в перспективе, возможно, было бы полезно нарисовать некоторые из наиболее распространенных форм кривых:

Как отмечалось выше, имеет значение только форма линии, а не ее наклон. На следующем рисунке:

... все линии прямые, поэтому, несмотря на то, что их наклоны радикально различаются, они по-прежнему все идентичны, насколько это важно для большого-O - все они просто O (N), независимо от наклона. С логарифмами мы получаем примерно тот же эффект — каждая линия будет искривлена, как линия O(log N) на предыдущем рисунке, но изменение основания логарифма повернет эту кривую вокруг начала координат, так что вы (снова) имеют одинаковую форму линии, но с разным наклоном (так что, опять же, насколько это важно, они все идентичны). Итак, переходя к первоначальному вопросу, если мы изменим основание логарифмов, мы получим кривые, которые выглядят примерно так:

Здесь может быть немного менее очевидно, что все, что происходит, — это постоянное изменение наклона, но здесь именно в этом разница, как и в случае с прямыми линиями выше.

Это потому, что изменение основания логарифма равносильно его умножению на константу. А большой O не заботится о константах.

log_a(b) = log_c(b) / log_c(a)

Таким образом, чтобы получить от log2(n) до log3(n), вам нужно умножить его на 1 / log(3) 2.

Другими словами log2(n) = log3(n) / log3(2).

log3(2) является константой, а O(cn) = O(n), таким образом, O (log2(n)) = O (log3(n))

Здесь уже есть несколько хороших ответов, поэтому, пожалуйста, прочитайте их тоже. Чтобы понять, почему Log2(n) равен O(log3(n)) вам нужно понять две вещи.

1) Что подразумевается под обозначением BigO. Я предлагаю прочитать это: http://en.wikipedia.org/wiki/Big_O_notation Если вы понимаете, это, вы будете знать, что 2n и 16n+5 оба O(N)

2) как работают логарифмы. разница между log₂ (N) и log₁₀(N) будет простым соотношением, которое легко вычислить, если вы хотите, согласно ответу luk32.

Поскольку журналы с разными основаниями отличаются только постоянным отношением а, а Большой О безразличен к второстепенным вещам, таким как постоянные коэффициенты умножения, вы часто обнаружите, что O(logN) на самом деле опускает основание, потому что выбор любого постоянного основания (например, 2, 3,10,e) в этом контексте не имеет значения.

Это зависит от контекста, в котором используется нотация O. Когда вы используете его в рассуждениях об алгоритмической сложности, вас интересует асимптотическое поведение функции, т. е. как она растет/убывает при стремлении (плюс-минус) к бесконечности (или к другой точке накопления).

Следовательно, хотя f(n) = 3n всегда меньше g(n) = 1000n, они оба появляются в O(n), поскольку они растут linearly (согласно их выражениям) асимптотически.

Тот же шаблон рассуждений можно использовать для случая логарифма, который вы опубликовали, поскольку логарифмы с разными основаниями различаются для постоянного фактора, но имеют одинаковое асимптотическое поведение.

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