Informatiker Board | Algorithmen

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » O(n) , O(log(n²))

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

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

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Tina92
unregistriert

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

Zitatantwort auf diesen Beitrag erstellen

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 09:36

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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]$

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 14.05.2015 10:47.

14.05.2015 10:47

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » O(n) , O(log(n²))