Bestimmung Anzahl der Operationen & Komplexität |
14.01.2017, 16:05 | Auf diesen Beitrag antworten » | ||
BeatleBlue | Bestimmung Anzahl der Operationen & Komplexität Hallo zusammen Ich habe gerade angefangen mich für die Prüfung im Fach Algorithmen vorzubereiten und bin schon jetzt bei der folgenden, eigentlich leichten, Aufgabe hängengeblieben.
Angegeben werden sollen nun die Anzahl der Operationen und die Komplexität. Ich hänge immer wieder bei ähnlichen Aufgaben, finde zwar immer irgendwie eine Lösung, allerdings dauert dies viel zu lange. Kann mir jemand erklären, wie das allgemeine Vorgehen bei solchen Aufgabenstellungen ist? Vielen Danke im voraus für eure Untersützung! Grüße! |
||
|
|||
22.01.2017, 00:19 | Auf diesen Beitrag antworten » | ||
joho | Bestimmung Anzahl der Operationen & Komplexität Hey, generell schaut man sich für alle Schritte eines Algorithmus an wie oft sie wiederholt werden und wieviele Schritte dort jeweils ausgeführt werden. Anschließend fasst man diese Schritte zusammen und vereinfacht sie (Konstanten sind nicht relevant, da sie für das Wachstum bei Betrachtung von großen nicht ausschlaggebend sind). Bei deinem Beispiel sollte das wie folgt aussehen: 1. Initialisieren von min und max. 2 Schritte und 1. wird nicht wiederholt. 2. paarweiser Vergleich und 2 Vergleich für min und max -> also 3 Schritte. 2. wird insgesamt für alle wiederholt. Also mal. Zusammen ist das für 2. Insgesamt wäre die Laufzeit also: , da sich die Konstanten und die aus kürzen lassen. Falls du noch Fragen hast gerne her damit. LG |
|