Zeitliche Komplexität eines Algorithmus: Ist es wichtig, die Basis des Logarithmus anzugeben?

19

Da es nur eine Konstante zwischen den Logarithmusbasen gibt, ist es nicht in Ordnung, zu schreiben , im Gegensatz zu oder was auch immer Basis könnte sein? $f(n) = \Omega(\log{n})$ $\Omega(\log_2{n})$

algorithms time-complexity Alex5207
quelle

1

Related / duplicate: Warum ist das Protokoll im Big-O der binären Suche nicht Basis 2?

Dukel

63

Es kommt darauf an, wo der Logarithmus ist. Wenn es sich nur um einen Faktor handelt, macht es keinen Unterschied, denn mit big-O oder können Sie mit jeder Konstanten multiplizieren. $\theta$

Wenn Sie ist die Basis wichtig. In Basis 2 hätten Sie nur , in Basis 10 geht es um . $O(2^{\log n})$ $O(n)$ $O(n^{0.3010})$

gnasher729
quelle

5

Ich denke, das wird nur zu so etwas wie . Ich kann keinen Grund dafür sehen, eine Zahl als auszudrücken, anstatt als -für-alles-was-es-ist (außer vielleicht als Zwischenstufe einer Berechnung).

2^{\sqrt{\log n}}

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

2^{c \log_{b} n}

$2^{c\log_b n}$

n

$n$

David Richerby

7

+1 für "Konstante Faktoren spielen in Exponenten eine Rolle"

Wahrsager

50

Da in der asymptotischen Notation konstante Faktoren nicht berücksichtigt werden und zwei beliebige Logarithmen sich um einen konstanten Faktor unterscheiden, macht die Basis keinen Unterschied: $\log_a n = \Theta(\log_b n)$ für alle $a,b > 1$ . Es ist also nicht erforderlich, die Basis eines Logarithmus anzugeben, wenn die asymptotische Notation verwendet wird.

Yuval Filmus
quelle

13

Ich ziehe es vor,

anstelle von

\in

$\in$

=

$=$

Nayuki

16

Ich fürchte, die Standardnotation verwendet

.

=

$=$

Yuval Filmus

4

@YuvalFilmus Die Standardnotation ist irreführend, unterscheidet sich völlig vom Standard und lässt die algorithmische Komplexität von ähnlichen Dingen völlig fremd erscheinen. "Es ist die Standardnotation" sollte niemals ein Grund sein, eine schlechte Lösung einer besseren, ähnlich klaren vorzuziehen. (Die Bedeutung des Symbols ergibt sich normalerweise ohnehin aus dem Kontext.)

wizzwizz4

7

@ wizzwizz4 Die gängige Praxis ist ein hervorragender Grund. Es fördert eine effiziente Kommunikation. Das ist der Grund, warum wir uns alle mit den Macken der englischen Rechtschreibung abfinden.

Yuval Filmus

3

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

15

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

Oh mein Gott
quelle

8

In den meisten Fällen ist es sicher, die Basis des Logarithmus zu löschen, da, wie andere Antworten gezeigt haben, die Formel zur Änderung der Basis für Logarithmen bedeutet, dass alle Logarithmen konstante Vielfache voneinander sind.

Es gibt einige Fälle, in denen dies nicht sicher ist. Zum Beispiel hat @ gnasher729 darauf hingewiesen, dass die logarithmische Basis in der Tat signifikant ist, wenn Sie einen Logarithmus in einem Exponenten haben.

$b$ $b$ $\Theta(n + b)$ $\log_b U$ $U$ $O((n + b) \log_b U)$ $b$ $O(n \log U)$ $b$ $b = n$ $O(n + \log_n U)$ $\log_n U$ $\frac{\log U}{\log n}$ $O(\frac{n \log U}{\log n})$ $\log_{m/2 + 2}$

$b$ $b$ $\Theta(\log_b n)$ $b$

Zusammenfassend können Sie in Fällen, in denen Sie einen Logarithmus mit einer konstanten Basis haben, normalerweise (vorbehaltlich von Ausnahmen wie @ gnasher729) die Basis des Logarithmus fallen lassen. Wenn die Basis des Logarithmus jedoch von bestimmten Parametern des Algorithmus abhängt, ist dies normalerweise nicht sicher.

templatetypedef
quelle

Zeitliche Komplexität eines Algorithmus: Ist es wichtig, die Basis des Logarithmus anzugeben?

Antworten: