Komplexität vom Algorithmus angeben: Ressourcenbedarf

[osion]

Hallo

Ich frage mich ob meine Berechnungen richtig sind.
Beispiel: Bei (2) erhalte ich n + 5n^2 oder n + n^2?

 

[Blender3D]

Beispiel: Bei (2) erhalte ich n + 5n^2 oder n + n^2?

eher: n + 10n = O(n)
doC(n) = O(n)
jedoch doC(5) = O(5) = O(1)

 

[osion]

eher: n + 10n = O(n)
doC(n) = O(n)
jedoch doC(5) = O(5) = O(1)

Also n + 10n = O(n) wäre die Lösung für die ganze Funktion?
Warum wird doC(5) zu O(1) und nicht O(5)?

 

[Blender3D]

Warum wird doC(5) zu O(1) und nicht O(5)?

O(5) entspricht O(1) das bedeutet eine konstante Laufzeit.

 

[KonradN]

Evtl. zur Erläuterung mal

O-Notation und Zeitkomplexität - anschaulich erklärt

Anschauliche Erklärungen mit Beispielen und Diagrammen: O-Notationen für die Komplexitätsklassen O(1), O(log n), O(n), O(n log n), O(n²)

www.happycoders.eu

ansehen.

Es geht um Komplexitätsklassen. Hier hast du einen konstanten Zeitbedarf. Dabei ist dann egal, ob dies 1, 5 oder 100 Schritte sind. O(1) ist die Angabe bei dieser Klasse.

Daher grob kleine Regeln:
Konstante Faktoren können entfallen: O(5) ist O(1). O(3n) ist O(n), …
Nur der höchste Part bei Additionen zählt: O(n^2+n) ist einfach O(n^2)

Es geht ja um ein Einordnung in eine Klasse bei großen n - und da spielt bei dem Quadrat dieses n keine Rolle mehr. 100 mal 100 — da ist dann ein +100 fast egal. Und 100 ist klein …. Bei 1.000.0000 wird das ja noch deutlicher….