Złożoność czasowa algorytmu: czy ważne jest określenie podstawy logarytmu?

Ponieważ między podstawami logarytmów jest tylko stała, to czy nie jest po prostu dobrze pisać $f(n) = \Omega(\log{n})$ , w przeciwieństwie do $\Omega(\log_2{n})$ , czy cokolwiek to może być podstawa?

To zależy od logarytmu. Jeśli jest to tylko czynnik, to nie ma znaczenia, ponieważ duże-O lub $\theta$ pozwala pomnożyć przez dowolną stałą.

Jeśli weźmiesz $O(2^{\log n})$ podstawa jest ważna. W bazie 2 miałbyś tylko $O(n)$ , w bazie 10 chodzi o $O(n^{0.3010})$ .

Ponieważ notacja asymptotyczna jest nieświadoma stałych czynników, a dowolne dwa logarytmy różnią się stałym współczynnikiem, zasada nie robi różnicy: $\log_a n = \Theta(\log_b n)$ dla wszystkich $a,b > 1$ . Nie ma więc potrzeby określania podstawy logarytmu przy stosowaniu notacji asymptotycznej.

Jako $\log_xy = \frac{1}{\log_y{x}}$ i$\log_x{y} = \frac{\log_z{y}}{\log_z{x}}$ , tak $\frac{\log_a{n}}{\log_b{n}} = \frac{\log_n{b}}{\log_n{a}} = \log_a{b}$. Ponieważ$\log_a{b}$jest dodatnią stałą (dla wszystkich$a,b > 1$), więc$\log_a{n} = \Theta(\log_b{n})$.

W większości przypadków bezpieczne jest upuszczenie podstawy logarytmu, ponieważ, jak wskazały inne odpowiedzi, formuła zmiany podstawy dla logarytmów oznacza, że ​​wszystkie logarytmy są stałymi wielokrotnościami.

W niektórych przypadkach nie jest to bezpieczne. Na przykład @ gnasher729 wskazał, że jeśli masz logarytm w wykładniku, to podstawa logarytmiczna jest rzeczywiście znacząca.

$b$$b$$\Theta(n + b)$$\log_b U$$U$$O((n + b) \log_b U)$$b$$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.