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

14.05.2015, 09:36	Auf diesen Beitrag antworten »
Tina92	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.


14.05.2015, 10:47	Auf diesen Beitrag antworten »
eulerscheZahl	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 $[latex]\mathcal{O}(n)[/latex]$ . Das Sortieren der Zahlen im Array nach der Größe ist schon komplizierter, je nach Algorithmus hast du hier typischerweise $[latex]\mathcal{O}(n \cdot \log(n))[/latex]$ oder $[latex]\mathcal{O}(n^2)[/latex]$

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »