Informatiker Board | Berechenbarkeits- und Komplexitätstheorie | Bestimmung Anzahl der Operationen & Komplexität

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Bestimmung Anzahl der Operationen & Komplexität

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Bestimmung Anzahl der Operationen & Komplexität

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

BeatleBlue
Grünschnabel

Dabei seit: 14.01.2017
Beiträge: 1

Bestimmung Anzahl der Operationen & Komplexität

Zitatantwort auf diesen Beitrag erstellen

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!

14.01.2017 16:05

Nehmen Sie BeatleBlue in Ihre Freundesliste auf

joho
Grünschnabel

Dabei seit: 21.01.2017
Beiträge: 4

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

22.01.2017 00:19

Nehmen Sie joho in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Bestimmung Anzahl der Operationen & Komplexität