Ist O (log n) immer schneller als O(n)
Wenn es zwei Algorithmen gibt, die dasselbe Ergebnis mit unterschiedlichen Komplexitäten berechnen, wird O (log n) immer schneller sein? Wenn ja, bitte erläutern. Übrigens ist dies keine Zuordnungsfrage.
Wenn ein Algorithmus in N/100 und der andere in (log N)*100 ausgeführt wird, ist der zweite Algorithmus bei kleineren Eingangsgrößen langsamer. Bei asymptotischen Komplexitäten geht es um das Verhalten der Laufzeit, wenn die Eingabegrößen ins Unendliche gehen.
Nein, es wird nicht immer schneller sein. ABER, mit zunehmender Problemgröße werden Sie mit eventuell immer an einem Punkt erreicht, an dem der Algorithmus O (log n) schneller ist als der Algorithmus O(n).
In realen Situationen würde der Punkt, an dem der O (log n) -Algorithmus den O(n) -Algorithmus überholen würde, sehr schnell kommen. Es gibt einen großen Unterschied zwischen O (log n) und O (n), genau wie zwischen O(n) und O (n ^ 2).
Wenn Sie jemals die Gelegenheit haben, Programming Pearls von Jon Bentley zu lesen, gibt es ein beeindruckendes Kapitel, in dem er einen O(n) - Algorithmus gegen einen O (n ^ 2) -Algorithmus setzt alles Mögliche tun, um O (n ^ 2) den Vorteil zu geben. (Er codiert den O (n ^ 2) - Algorithmus in C auf einem Alpha und den O(n) - Algorithmus in BASIC auf einem alten Z80 oder etwas, das bei etwa 1 MHz läuft.] Es ist überraschend, wie schnell der O(n) - Algorithmus überholt den O (n ^ 2) - Algorithmus.
Gelegentlich finden Sie jedoch einen sehr komplexen Algorithmus, dessen Komplexität etwas besser ist als der einfachere. Wählen Sie in einem solchen Fall den Algorithmus nicht blind mit einem besseren Big-O - Sie werden feststellen, dass er nur bei extrem großen Problemen schneller ist.
Für die Eingabe der Größe n führt ein Algorithmus von O(n) Schritte aus, die proportional zu n sind, während ein anderer Algorithmus von O(log(n)) Schritte ausführt, die protokollieren ( n).
Log (n) ist eindeutig kleiner als n, daher ist der Algorithmus der Komplexität O(log(n)) besser. Da wird es viel schneller.