Mergesort Laufzeit BIGO

Question

Snapes „Unfreundliche Algorithmen für Wizards“ Lehrbuch behauptet, die Laufzeit von merge sort ist O (n ^ 4). Ist diese Behauptung richtig?

Lösung: Ja. Dieser Anspruch ist technisch korrekt, da O (n ^ 4) gibt nur einen oberen gebunden, wie lange der Algorithmus nimmt. Allerdings ist es ein obnoxiously nicht hilfreich Antwort, da die dicht gebunden ist Θ(n log n).

verstehe ich nicht ganz, was die Lösung unter Angabe. Wie kann O (n ^ 4) richtig sein?

Answer 1

Big O-Notation ist eine Oberegrenze auf den schlimmsten Fall für einen Algorithmus Laufzeit.

Da O (n ^ 4) über dem schlimmsten Fall Zeit von mergesort ist es technisch korrekt, weil es sich um eine nicht gebunden fühlt liefern - dh. Mergesort wird nie eine Leistung schlechter als O hat (n ^ 4).

Allerdings ist es nicht hilfreich, da ein besserer Ausdruck der Laufzeit ist O (n log n), die die „engste“ für Mergesort gebunden ist

Answer 2

Big-O ist ein Satz, der alles beinhaltet, dass läuft so schnell wie (foo) oder schneller. Little-O ist eine Reihe von Dingen, die streng schneller als (foo) laufen. Während es richtig ist mergesort zu sagen, ist O (n ^ 4), es ist nicht sehr nützlich, weil es Theta ist (n log n). dass mergesort sagen will ist, o (n ^ 4) ist geringfügig mehr sinnvoll, da wenig-o-Notation wird verwendet, nie groß-Theta-Laufzeit zu bedeuten.

Erschwerend kommt, Big-O wird häufig verwendet, wenn Big-Theta wäre besser geeignet, nur weil die meisten Tastaturen haben keine Theta.