Wie lange dauert es, 10610610^6 Zahlen und 10910910^9 Zahlen für zwei Algorithmen zu sortieren, wenn sie die gleiche Zeit brauchen, um 100010001000 Zahlen zu sortieren?

Wie es heißt, lautet die Antwort "wir wissen es nicht". Es folgt aus der$O(\cdot)$Notation - grob gesagt, Sie haben nicht genug Informationen, um auf irgendetwas zu schließen. Sie kennen nur das asymptotische Verhalten und nicht einmal die Konstanten.

Algorithmus 1 könnte genauso schnell sein wie Algorithmus 2 solange$n$ist kleiner als, sagen wir,$10^{10}$, und bricht dann zusammen.

Schlimmer noch, die Big-Oh-Notation ist nur eine Obergrenze. Soweit wir wissen, könnten beide die gleiche Laufzeit haben$O(n\log n)$, da wenn Algorithmus 1 Laufzeit hätte$O(n\log n)$, es hätte trivialerweise auch Laufzeit$O(n^2)$.

Sie haben zwei Antworten gesehen, die veranschaulichen, dass Big-O-Timing-Schätzungen nicht viel über die tatsächlichen Laufzeiten aussagen, aber um zu veranschaulichen, wie groß der Unterschied zwischen den tatsächlichen Bestellungen ist, lassen Sie uns auf die Big-O-Schätzungen verzichten und annehmen, dass wir es tatsächlich wüssten dass Algorithmus 1 genau genommen hat$c_1n^2$Sekunden zu sortieren$n$Zahlen und Algorithmus 2 nahm genau$c_2n\log_{10} n$Sekunden zu sortieren$n$Zahlen (ich habe log zur Basis zehn gewählt, um die Berechnungen zu vereinfachen; die Wahl einer anderen Basis würde nur die Konstante ändern$c_2$).

Wenn Algorithmus 2 zum Sortieren 1 Sekunde brauchte$10^3$Zahlen, hätten wir

$$1=c_1(10^3)^2=c_1\,10^6$$ So $c_1=1/10^6$. Wenn Algorithmus 2 auch 1 Sekunde zum Sortieren brauchte $10^3$Zahlen, hätten wir $$1=c_2(10^3\log(10^3))=c_2(3\cdot10^3)$$ So $c_2=1/(3\cdot10^3)$.

Nun wollen wir sehen, was passiert, wenn wir sortieren$10^6$Zahlen. Algorithmus 1 übernimmt

$$\frac{1}{10^6}\cdot(10^6)^2=\frac{10^{12}}{10^6}=10^6\text{ seconds}$$ was ungefähr funktioniert $11.5$Tage. Andererseits übernimmt Algorithmus 2 $$\frac{1}{3\cdot10^3}\cdot(10^6\log10^6)=\frac{6\cdot10^6}{3\cdot10^3}=2\cdot10^3\text{ seconds}$$ worum es geht $33.3$Protokoll. Hmm, 11 Tage statt einer halben Stunde. Ich weiß, welchen Algorithmus ich verwenden würde.

Bei größeren Eingaben wird der Zeitunterschied sogar noch dramatischer. Mit$10^9$Zahlen zu sortieren, können Sie ausrechnen, dass Algorithmus 1 ungefähr 31688 Jahre brauchen würde , während Algorithmus 2 ungefähr 34,7 Tage brauchen würde.

Beachten Sie, dass Algorithmus 1 einen viel kleineren konstanten Multiplikator als Algorithmus 2 hatte, aber auf lange Sicht war das nicht annähernd so wichtig wie die asymptotische Reihenfolge ihrer Laufzeiten. Einfach gesagt, ein$n\log n$Algorithmus wird schließlich ein schlagen$n^2$Algorithmus, egal wie das konstante Vielfache ist.

Mathematisch, groß-$O$Notation funktioniert so nicht.$O(n^2)$bezeichnet eine Äquivalenzklasse von Funktionen basierend auf ihrer Asmyptotik.

Also zum Beispiel$f$definiert von$f(n)=n^2$gehört$O(n^2)$. Ebenso die Funktion$g$definiert von$g(n)=10^{1000}n^2$.

Also zwei verschiedene Algorithmen, die Zeit brauchen$O(n^2)$kann für eine bestimmte Aufgabe immer noch eine sehr unterschiedliche Leistung haben. Der große-$O$Notation soll die Skalierbarkeit dieser Algorithmen als erfassen$n \rightarrow \infty$.

---

Wenn Sie dies jedoch für eine praktische Anwendung verwenden, wird die multiplikative Konstante vorne wahrscheinlich nicht zu groß sein. Ignorieren der$O(..)$kann oft eine vernünftige Intuition geben, wie lange der Algorithmus dauern wird.

Wir könnten uns also annähern, dass die$O(n^2)$Der Algorithmus würde einige Zeit in Anspruch nehmen$(10^6)^2=10^{12}$herstellen$10^6$Gegenstände und die$O(n \log n)$Der Algorithmus würde einige Zeit in Anspruch nehmen$10^9 \log {10^9} \approx 2 \times 10^{10}$herstellen$10^9$Artikel.

In den meisten realen Fällen wird der Vergleich nicht allzu schlecht sein, aber andererseits könnte er auch schrecklich sein.