Временная сложность алгоритма: важно ли указать основание логарифма?

Поскольку существует только константа между основаниями логарифмов, не так ли просто написать $f(n) = \Omega(\log{n})$ , в отличие от $\Omega(\log_2{n})$ , или какова бы ни была база?

Это зависит от того, где находится логарифм. Если это просто фактор, то это не имеет значения, потому что big-O или $\theta$ позволяет вам умножить на любую константу.

Если вы берете $O(2^{\log n})$ то база важна. В базе 2 у вас будет только $O(n)$ , в базе 10 - около $O(n^{0.3010})$ .

Поскольку асимптотические обозначения не учитывают постоянные множители, а любые два логарифма отличаются постоянным множителем, основание не имеет значения: $\log_a n = \Theta(\log_b n)$ для всех $a,b > 1$ . Таким образом, нет необходимости указывать основание логарифма при использовании асимптотической записи.

As $\log_xy = \frac{1}{\log_y{x}}$ и$\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$ , поэтому $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$$\log_a{b}$$a,b > 1$$\log_a{n} = \Theta(\log_b{n})$

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

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

Я хотел указать на другой случай, когда основание логарифма является значительным, и это случаи, когда основание логарифма напрямую зависит от параметра, указанного в качестве входного значения для задачи. Например, алгоритм сортировки по основанию работает, выписывая числа в некоторой базе$b$разложение входных чисел на их базовые$b$цифры, затем с помощью сортировки подсчета, чтобы отсортировать эти числа по одной цифре за раз. Работа за раунд$\Theta(n + b)$ и есть примерно $\log_b U$ раунды (где $U$ максимальное входное целое число), поэтому общее время выполнения $O((n + b) \log_b U)$. For any fixed integer $b$ this simplifies to $O(n \log U)$. However, what happens if $b$ isn't a constant? A clever technique is to pick $b = n$, in which case the runtime simplifies to $O(n + \log_n U)$. Since $\log_n U$ = $\frac{\log U}{\log n}$, the overall expression simplifies to $O(\frac{n \log U}{\log n})$. Notice that, in this case, the base of the logarithm is indeed significant because it isn't a constant with respect to the input size. There are other algorithms that have similar runtimes (an old analysis of disjoint-set forests ended up with a term of $\log_{m/2 + 2}$ somewhere, for example), in which case dropping the log base would interfere with the runtime analysis.

Another case in which the log base matters is one in which there's some externally-tunable parameter to the algorithm that control the logarithmic base. A great example of this is the B-tree, which requires some external parameter $b$. The height of a B-tree of order $b$ is $\Theta(\log_b n)$, where the base of the logarithm is significant in that $b$ is not a constant.

To summarize, in the case where you have a logarithm with a constant base, you can usually (subject to exceptions like what @gnasher729 has pointed out) drop the base of the logarithm. But when the base of the logarithm depends on some parameter to the algorithm, it's usually not safe to do so.