Komplexität grundlegender Operationen von Such- und Sortieralgorithmen [geschlossen]

Wiki hat ein gutes Spickzettel, aber es beinhaltet kein Nein. von Vergleichen oder Swaps. (obwohl die Anzahl der Swaps normalerweise über ihre Komplexität entscheidet). Also habe ich folgendes erstellt. Ist die folgende Information korrekt? Bitte lassen Sie mich wissen, wenn ein Fehler vorliegt, ich werde ihn korrigieren.

Sortieren durch Einfügen:

• Durchschnittlicher Fall / schlimmster Fall: ; tritt auf, wenn die Eingabe bereits in absteigender Reihenfolge sortiert ist$\Theta(n^2)$
• Bester Fall: ; wenn die Eingabe bereits sortiert ist$\Theta(n)$
• Anzahl der Vergleiche: im schlechtesten Fall & Θ ( n ) im besten Fall$\Theta(n^2)$$\Theta(n)$
• $\Theta(n^2)$$0$

Auswahl Sortieren:

• $\Theta(n^2)$
• $\Theta(n^2)$
• $\Theta(n)$$0$

Zusammenführen, sortieren :

• $\Theta(nlgn)$
• $\Theta(n+m)$$\Theta(n)$$n<m$
• Anzahl der Swaps: Keine Swaps! [erfordert aber zusätzlichen Speicher, keine In-Place-Sortierung]

Schnelle Sorte:

• $\Theta(n^2)$
• $\Theta(nlogn)$
• $\Theta(n^2)$$\Theta(nlogn)$
• $\Theta(n^2)$$0$

Blasensortierung:

• $\Theta(n^2)$
• $\Theta(n)$
• $\Theta(n^2)$
• $\Theta(n^2)$$0$

Lineare Suche:

• $\Theta(n)$
• $\Theta(1)$
• $\Theta(n)$$1$

Binäre Suche:

• $\Theta(logn)$
• $\Theta(1)$
• $\Theta(logn)$$1$

1. Ich habe nur grundlegende Such- und Sortieralgorithmen berücksichtigt.
2. Es wird oben angenommen, dass Sortieralgorithmen eine Ausgabe in aufsteigender Reihenfolge erzeugen
3. Quellen: Das großartige CLRS und dieses Wiki

$\Theta(n^2)$$n$

$n^2$