Informatiker Board | Druckvorschau: Bestimmung Anzahl der Operationen & Komplexität

Geschrieben von BeatleBlue am 14.01.2017 um 16:05:

Bestimmung Anzahl der Operationen & Komplexität

Hallo zusammen Wink

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.

Zitat:

Gegeben sei ein Feld (array) F mit n nicht sortierten Zahlen. Sie wollen das Minimum und das Maximum der n Zahlen bestimmen
Sie initialisieren min mit F[0] und max mit F[0]. Danach
vergleichen Sie immer paarweise F[i] und F[i+1] für alle ungeraden i, d.h. Sie vergleichen
F[1] mit F[2], danach F[3] mit F[4], usw. Das jeweils kleinere Element dieser Paare
vergleichen Sie mit dem bisherigen Minimum, das jeweils größere Element mit dem
bisherigen Maximum. (Der Einfachheit halber können Sie annehmen, dass n ungerade ist.)

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!

Geschrieben von joho am 22.01.2017 um 00:19:

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 [latex]n[/latex]

nicht ausschlaggebend sind).

Bei deinem Beispiel sollte das wie folgt aussehen:

1. Initialisieren von min und max. 2 Schritte und 1. wird nicht wiederholt. [latex]O(2)[/latex]

2. paarweiser Vergleich und 2 Vergleich für min und max -> also 3 Schritte. 2. wird insgesamt für alle [latex]i=1,3,5,...,n[/latex]

wiederholt. Also $[latex]\frac{n}{2}[/latex]$ mal. Zusammen ist das für 2. $[latex]O(3 * \frac{n}{2}) = O(\frac{3}{2}* n)[/latex]$

Insgesamt wäre die Laufzeit also:
$[latex]O(O(2) + O(\frac{3}{2}* n)) [/latex]$
$[latex]\Rightarrow O(O(\frac{3}{2}* n))[/latex]$
$[latex]\Rightarrow O( O( n))[/latex]$
$[latex]\Rightarrow O(n)[/latex]$ , da sich die Konstanten [latex]O(2)[/latex]

und die $[latex]\frac{3}{2}[/latex]$ aus $[latex]O(\frac{3}{2}* n)[/latex]$ kürzen lassen.

Falls du noch Fragen hast gerne her damit.

LG