QuickSort Zeitkomplexität (Big-O)

QuickSort läuft im Mittel in O(n log n) und im Worst Case in O(n²), mit O(log n) Speicher. Es ist ein Divide-and-Conquer-Vergleichssort mit Pivot und In-Place-Partition; die randomisierte Variante liefert O(n log n) erwartet.

Wichtige Fakten

Häufige Fragen

Wie ist die Zeitkomplexität von QuickSort?

O(n log n) im Mittel, O(n²) im Worst Case.

Wann erreicht QuickSort O(n²)?

Bei bereits sortierter Eingabe mit Pivot am Ende (letztes Element).

Verwandte Seiten

• HTTP 200 OK
• HTTP 301 Moved Permanently
• HTTP 401 Unauthorized
• HTTP 403 Forbidden
• HTTP 404 Not Found
• HTTP 429 Too Many Requests
• HTTP 500 Internal Server Error
• HTTP 502 Bad Gateway

Big-O von QuickSort ist Teil von DevRef Hub auf GOAT Lab — eine kostenlose Referenz, die ohne Anmeldung und auch offline funktioniert. Öffne oben das Tool für beliebige Werte.

Werbung

Teil von GOAT Lab — 26 kostenlose Browser-Tools für Wissenschaft, Technik und Entwicklung. Ohne Anmeldung.