---

Geschrieben von Tina92 am 14.05.2015 um 09:36:

  O(n) , O(log(n²))

Meine Frage:
Hallo zusammen,

momentan beschäftige ich mit der Laufzeitkomplexität T(n) bei Algorithmen. Da kommen mir auch immer wieder die Begriffe O(n) , O(log(n²)) unter. Was haben diese denn genau für einen Sinn?

Meine Ideen:
Vielen Dank.

---

Geschrieben von eulerscheZahl am 14.05.2015 um 10:47:

 

Wenn du eine Operation mit Daten durchführst, hängt es von der Beschaffenheit dieser ab, wie lange die Operation dauert.
Beispiel:
Du hast ein Array von 10 Zahlen und willst die Summe berechnen. Dafür musst du dir jede Zahl einmal ansehen und auf die bisherige Summe addieren, brauchst also 10 Additionen. Bei 100 Zahlen sind es schon 100 Additionen, die Laufzeit wächst linear mit der Arraygröße, also .
Das Sortieren der Zahlen im Array nach der Größe ist schon komplizierter, je nach Algorithmus hast du hier typischerweise oder