Frage von leonardomessi, 19

Big O-Notation?

Also für die Leute die es verstehen habe ich eine Streber frage und zwar es interessiert mich warum, z.b die Funktion: 2n^2 + 4 die die Laufzeit O(n^2) hat, keine n^3 enthalten kann. Also sei c>=0, dann n^c+1 kein Element von O(n^c)

Antwort
von kxell2001, 6

Die O-Notation beschreibt die worst-case Laufzeit zur Eingabengröße (in deinem Beispiel ist die Variable n die Eingabegröße). In deinem Beispiel ist also 2n^2 + 4 somit O(n^2). 

Heisst seeeeehr vereinfacht ausgedrückt, dass die Funktion in der Klammer im schlechtesten Fall diesen Wachstum hat und hierbei werden alle Konstanten ignoriert und nur die Variablen der Eingabengrößen werden betrachtet. In deinem Beispiel ist es k * n^2 + k mit k = konstante. Streicht man alle k's, dann bleibt nur noch n^2. Und da n^2 < n^3 gilt, kann es somit keine n^3 haben, da wie schon gesagt in der O-Notation die maximale "Wachstumsrate" angegeben wird.

und da bei n^(c+1), die Variable n vom Exponenten abhängt, ist c+1, insbesondere die 1 keine Konstante die man ignorieren darf.


Keine passende Antwort gefunden?

Fragen Sie die Community