Frage von mario1997, 20

Was bedeutet quasilinearer Aufwand?

Habe bald eine Präsentation über Aufwandsabschätzung bei Sortieralgorithmen und weiß nicht wofür n log n und quasilinearer aufwand stehen

Antwort
von User440923, 9

Diese Angabn beziehen sich auf sog. Obere Schranken für die Laufzeit des Algorithmus bei einer Eingabe mit der Länge n (d.h. n Elemente im Array). (Siehe auch Landau-Symbole). Das Quasi linear kommt daher, dass n log n zwar schneller wächst als eine lineare Funktion aber langsamer als jede Polynomfunktion mit einem Grad größer 1. Deshalb nennt man dies quasi (=fast) linear.

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten