Почему журнал в биг-о двоичного поиска не является базой 2?

Я новичок в понимании алгоритмов информатики. Я понимаю процесс бинарного поиска, но у меня возникло небольшое недопонимание с его эффективностью.

При размере элементов в среднем потребуется шагов, чтобы найти конкретный элемент. Взяв логарифм с обеих сторон 2, получим . Так не будет ли среднее число шагов для алгоритма бинарного поиска ? n $s = 2^n$$n$log 2 ( s $\log_2(s) = n$$\log_2(s)$

В этой статье Википедии об алгоритме двоичного поиска говорится, что средняя производительность равна . Почему это так? Почему это не число ?$O(\log n)$$\log_2(n)$

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

Например где C=

$$\log_{10}n = \frac{\log_{2}n}{\log_{2}10} = C \log_{2}{n}$$ .$C = \frac{1}{\log_{2}10}$

Таким образом, и log 2 n отличаются константой C , и, следовательно, оба являются истинными: log 10 n  - это  O ( log 2 n ), log 2 n  - это  O ( log 10 n ). В общем случае log a n - это O ( log b n ) для натуральных чисел a и b больше 1.$\log_{10}n$$\log_{2}n$$C$

$$\log_{10}n \text{ is } O(\log_{2}n)$$ $$\log_{2}n \text{ is } O(\log_{10}n)$$ $\log_{a}{n}$$O(\log_{b}{n})$$a$$b$

Еще один интересный факт с логарифмическими функциями является то , что в то время как при постоянном , п к НЕ О ( п ) , но войти н к является O ( журнал N ) , поскольку журнал п к = K лог н , который отличается от бревна п только константы фактор к .$k>1$$n^k$$O(n)$$\log{n^k}$$O(\log{n})$$\log{n^k} = k\log{n}$$\log{n}$$k$

In addition to fade2black's answer (which is completely correct), it's worth noting that the notation "$\log(n)$" is ambiguous. The base isn't actually specified, and the default base changes based on context. In pure mathematics, the base is almost always assumed to be $e$ (unless specified), while in certain engineering contexts it might be 10. In computer science, base 2 is so ubiquitous that $\log$ is frequently assumed to be base 2. That wikipedia article never says anything about the base.

But, as has already been shown, in this case it doesn't end up mattering.