Laufzeit eines Algorithmus

Aufrufe: 133     Aktiv: vor 3 Wochen, 6 Tagen

0

Wie kommt man auf die Laufzeit eines Algorithmus? Ich mein, wenn diese Konstant ist komm ich drauf. Auch ist mir klar das for- Schleifen oder änliches O(n) Zeit benötigen. Aber weiter? Wie zum beispuel weiß ich wenn es logn oder nlogn oder etwas noch komlizierteres ist? Und kann man immer infach O() hinschreiben? Weil das O mit dem Strich durch die Mitte und so gibt es ja auch noch.

gefragt vor 3 Monaten, 2 Wochen
s
sarah12345677,
Student, Punkte: 10

 
Kommentar schreiben Diese Frage melden
3 Antworten
0

Hallo, es gibt in der Tat triviale Laufzeiten, z. B. wenn man immer über alle Elemente einer Liste geht, hat man O(n). Würde man dabei pro Schritt nochmals über die Liste gehen, O(n^2). Ansonsten sind die Zusammenhänge meist nicht so einfach. Wichtig zu wissen ist, dass innerhalb der Klammern das geschrieben wird, dass den Algorithmus in Kombination mit der gewählten Datenstruktur am stärksten beschreibt. Es lohnt sich, gerade im Studium, die wichtigsten Vertreter und ihre Laufzeiten zu kennen. Dort lernt man auch Verfahren, um die Laufzeit abzuschätzen.

Auf YouTube gibt es Vorlesungen zum Thema, oder ganz klassische Literatur.

geantwortet vor 3 Monaten, 2 Wochen
pythonmeister
Teamleiter Softwareentwicklung, Punkte: 10
 
Kommentar schreiben Diese Antwort melden
0

O(logn) kommt immer dann vor, wenn man etwas immer weiter zur Hälfte aufteilt. Beispielsweise bei einer binären Suche, wenn man am Anfang eine List der Länge n hat, im zweiten Schritt eine Liste der Länge n/2 usw... die Schritte insgesamt bei einer solchen Liste sind eben log(n) lang.

geantwortet vor 4 Wochen
d
 
Kommentar schreiben Diese Antwort melden
0

Als Ergänzung zu den Antworten: typische Laufzeiten mit Beispielen sind:

O(log n): logarithmischer Aufwand. Problemgröße halbiert sich in jedem Schritt z.B. Binärsuche

O(n): linearer Aufwand. alle Elemente werden betrachtet z.B. Lineare Suche

O(n*log n): linear-logarithmischer Aufwand. typisch für Sortieralgorithmen

O(n²): quadratischer Aufwand. alle Paare werden betrachtet

geantwortet vor 3 Wochen, 6 Tagen
h
 
Kommentar schreiben Diese Antwort melden