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

19

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?

algorithms time-complexity

— Alex5207
źródło

1

Powiązane / zduplikowane: Dlaczego log w dużym O wyszukiwania binarnego nie jest bazą 2?

— Dukeling

63

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})$ .

— gnasher729
źródło

5

Myślę, że to tylko wymyśli coś takiego jak

. Nie widzę powodu, aby wyrażać liczbę jako

zamiast

-to-the-cokolwiek to jest (z wyjątkiem być może jako pośredniego etapu obliczeń).

2^{\sqrt{\log n}}

$2^{\sqrt{\log n}}$

2^{c \log_{b} n}

$2^{c\log_b n}$

n

$n$

— David Richerby

7

+1 za „stałe czynniki mają znaczenie w wykładnikach”

— trognanders

50

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.

— Yuval Filmus
źródło

13

Wolę zobaczyć

zamiast

\in

$\in$

=

$=$

— Nayuki

16

Obawiam się, że standardowa notacja używa

.

=

$=$

— Yuval Filmus

4

@YuvalFilmus Standardowa notacja wprowadza w błąd, zupełnie różni się od standardu wszędzie indziej i sprawia, że złożoność algorytmu wydaje się zupełnie obca od rzeczy całkiem podobnych do niego. „To standardowa notacja” nigdy nie powinna być powodem do faworyzowania złego rozwiązania nad lepszym, podobnie klarownym. (W każdym razie znaczenie tego symbolu jest zazwyczaj jasne.)

— wizzwizz4

7

@ wizzwizz4 Powszechna praktyka jest doskonałym powodem. Promuje sprawną komunikację. Właśnie dlatego wszyscy znosimy dziwactwa angielskiej pisowni.

— Yuval Filmus

3

Czasami

po prostu zawiera zbyt wiele rzeczy, aby było jaśniejsze niż

.

n \mapsto \log_{a} n \in Θ (n \mapsto \log_{b} n)

$n \mapsto \log_a n \in \Theta ( n \mapsto \log_b n)$

\log_{a} n = Θ (\log_{b} n)

$\log_a n = \Theta (\log_b n)$

— JiK

15

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})$ .

— O mój Boże
źródło

8

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.

— templatetypedef
źródło