(merge sort) ist log von n log n auf base 2?

Question

ich in der Klasse gelernt haben, die Art einfädelt O (n   ·   log (n)), aber ich bin auf dem nicht klar, ob es O (n   ·   log ( n)) oder O (n     · log (n)). Ich habe auf Stack Overflow (unter Big O notation Log Base 2 or Log Base 10) gelesen, dass "es keine Rolle spielt", weil sie ungefähr die gleiche Laufzeit geben; aber ich will die genaue Laufzeit. Zum Beispiel weiß ich, dass die Blasensortierung mit 512 Elementen 512²/2   -   512/2   =   130816 Zeiteinheiten; mergt 512 =   4608 Zeiteinheiten oder 512   ·   5.404   =   2767 Zeiteinheiten?

Answer 1

Seit merge sort teilt die Arrays zu Hälften, dann yup, Basis 2. Wie die Kommentare sagen, ist die Basis ein konstanter Faktor, so ist es nicht wichtig in großen O-Notation.

Answer 2

Ja, es ist auf Basis 2 anmelden, aber Sie können den Algorithmus ändern und das Array in 3 Teile aufteilen, und dann ist es log_3 (n), 4 Teile ist Base-4, und so weiter. ist es wirklich (wirklich) egal.

Answer 3

Ihre Frage basiert auf einer fehlerhaften Prämisse.

Angenommen, ich habe zwei äquivalente Algorithmen, A und B. Algorithmus A führt zehn Additionen und keine Multiplikationen durch; Algorithmus B führt eine Multiplikation und keine Additionen durch.

Algorithmische Analyse besagt, dass A und B sind Konstant-Zeit-Algorithmen (O (1)). Sie würden sie offensichtlich unterscheiden und sagen, dass (1) nur "ungefähr" ist, aber dass die "exakte" Laufzeit für A 10 ist und die "exakte" Laufzeit für B 1 ist, so dass A zehnmal ist schneller als B. Das scheint vernünftig. Aber vielleicht ist auf diesem Computer die Multiplikation doppelt so teuer wie die Addition, so dass der Unterschied tatsächlich mehr wie 10: 2 (d. H. 5: 1) ist. Oder umgekehrt sind die Kosten für das Fortschreiten von einem Befehl zum nächsten (Erhöhen des Programmzählers) so teuer wie die Kosten einer arithmetischen Operation, so dass der Unterschied tatsächlich eher 19: 1 ist. Oh, außer dass wir Speicheroperationen, die normalerweise viel teurer als arithmetische Operationen sind, nicht einmal in Betracht gezogen haben; Woher kommen die Werte in diesen Algorithmen?

Also, wenn Sie genaue Laufzeiten wollen, ist algorithmische Analyse nicht der richtige Ansatz; Der Grund, dass es konstante Faktoren verwirft (Log entspricht Log) ist, dass sonst viel, viel mehr Informationen über die Hardware und den Programmkontext und so weiter erfordern würde, die die Ergebnisse viel weniger machen würde allgemein anwendbar.

Stattdessen verwenden Sie Benchmarking — und für ein kleines Beispiel wie Ihres, das bedeutet microbenchmarking.