Was ich denke, verstehe ich.
Im schlimmsten Fall wählt der Schnellsortieralgorithmus den größten oder kleinsten Schlüssel in Liste/Array aus, der für jeden rekursiven Aufruf (bei rekursiver Implementierung) sortiert werden soll. Ich verstehe, dass die Größe von n sowohl die Anzahl der rekursiven Aufrufe als auch die Anzahl der Vergleiche bestimmt (die sich mit jedem Schritt der Rekursion um 1 verringern). Also haben wir insgesamt n + (n-1) + (n-2) + ... + 2 + 1 Primitivvergleichszahl.Große O-Zeit-Komplexität von Worst-Case-Quick-Sort?
Was ich nicht verstehe.
Der Teil, den ich nicht ganz verstehe, ist, wie das ist O (n^2)? Wie ich weiß, ist es mindestens O (n^2) als n + (n-1) + (n-2) + ... + 2 + 1 < n^2 aber woher weiß ich, dass es nicht O ist (n * logn)? Muss ich dieses Ergebnis beweisen, um sicher zu bestätigen, dass es O (n^2) ist oder ist das auf eine Weise, die ich nicht sehen kann, sofort offensichtlich? Ich denke im Allgemeinen, woher weiß ich, dass ich die niedrigste Funktion gefunden habe, die die große O-Zeit-Komplexität darstellt.