Was bedeutet quasilinearer Aufwand?

1 Antwort

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.

Was möchtest Du wissen?