Hallo,
ich schreibe bald eine Klausur in IV(Informationsverarbeitung) und der Inhalt wird eine Aufwandsabschätzung eines Algorithmus sein. Dazu gehört auch eine Funktionsgleichung der ZAW (Zentralen Anweisung) zu bestimmen.
Wie kann ich jetzt anhand eines Struktogrammes wie z.B von Bubblesort jetzt die Funktionsgleichung herausbekommen?
Vielen Dank schonmal für eure Hilfe
ich schreibe bald eine Klausur in IV(Informationsverarbeitung) und der Inhalt wird eine Aufwandsabschätzung eines Algorithmus sein. Dazu gehört auch eine Funktionsgleichung der ZAW (Zentralen Anweisung) zu bestimmen.
Wie kann ich jetzt anhand eines Struktogrammes wie z.B von Bubblesort jetzt die Funktionsgleichung herausbekommen?
Vielen Dank schonmal für eure Hilfe
Hi,
genau das ist auch mein Problem. Wir schreiben morgen IV.
Unser Lehrer hat es unz zwar erklärt aber richtig verstanden hab ich das nicht.
Also ich weiß so viel:
1. Aussuchen ob man nach Laufzeit oder Speicher untersuchen will
(wir haben immer Laufzeit gewählt)
2. Die Zentrale Anweisung finden
hier kannst du auswählen zwischen:
- Wert kopieren
- Wert vergleichen
- Wert verrechnen
3. Funktionsgelcihung aufstellen
Aber genau hier komme ich nicht weiter. Die Zentrale Anweisung fin ich noch und dann???
genau das ist auch mein Problem. Wir schreiben morgen IV.
Unser Lehrer hat es unz zwar erklärt aber richtig verstanden hab ich das nicht.
Also ich weiß so viel:
1. Aussuchen ob man nach Laufzeit oder Speicher untersuchen will
(wir haben immer Laufzeit gewählt)
2. Die Zentrale Anweisung finden
hier kannst du auswählen zwischen:
- Wert kopieren
- Wert vergleichen
- Wert verrechnen
3. Funktionsgelcihung aufstellen
Aber genau hier komme ich nicht weiter. Die Zentrale Anweisung fin ich noch und dann???
Was meint ihr mit Funktionsgleichung?
Ich könnte euch aus dem Struktogramm sagen wie man das in C umsetzen würde, aber ob das weiterhilft?
Ich könnte euch aus dem Struktogramm sagen wie man das in C umsetzen würde, aber ob das weiterhilft?
Ich gehe mal davon aus, da eine Aufwandsabschätzung gemacht werden möchte, dass die o-Notation (gibt Art des Wachstums eines A. an) des Algorithmus' gesucht ist.
In deinem Beispiel hängt viel von der Beschaffenheit der Liste ab, da die Liste z.B. sortiert sein kann oder ganz ungünstig sortiert ist. Allgemein kann man sagen, dass man die o-Notation häufig anhand der Schleifen-Zahl ablesen kann.
Im worst-case (Umgekehrt sortierte Liste) hat der Algorithmus einen Aufwand von o(n^2). n beschreibt die Anzahl der Elemente der Liste. Man kann übrigens glaube ich eine Formel angeben, die direkt die Anzahl der Schritte berechnet. Daraus leitet sich auch die o-Notation ab.
Im best case geht der Algorithmus einmal die Liste durch und bemerkt, dass die Liste richtig sortiert ist, daher o(n).
In deinem Beispiel hängt viel von der Beschaffenheit der Liste ab, da die Liste z.B. sortiert sein kann oder ganz ungünstig sortiert ist. Allgemein kann man sagen, dass man die o-Notation häufig anhand der Schleifen-Zahl ablesen kann.
Im worst-case (Umgekehrt sortierte Liste) hat der Algorithmus einen Aufwand von o(n^2). n beschreibt die Anzahl der Elemente der Liste. Man kann übrigens glaube ich eine Formel angeben, die direkt die Anzahl der Schritte berechnet. Daraus leitet sich auch die o-Notation ab.
Im best case geht der Algorithmus einmal die Liste durch und bemerkt, dass die Liste richtig sortiert ist, daher o(n).
@blra: Du sprichst hier von einem optimierten Algorithmus; bei dem im Struktogramm dargestellten Algorithmus hängt die Komplexiät nur von max ab (siehe unten)
Die "zentrale Anweisung" ist ja der Vergleich feld[j] > feld[j+1].
Also schauen wir uns einfach mal an, wie oft diese ausgeführt wird (den Algorithmus einfach mal im Kopf durchgehen):
max=1 --> 1-mal
max=2 --> (2+1) mal
max=3 --> (3+2+1) mal
max=4 --> (4+3+2+1) mal
allgemein: 1+2+3+...+max mal
Nach der gaußschen Summenformel gilt:
1+2+3+...+max = ( max*(max+1) ) / 2
=(max²+max)/2
Bei der Komplexität (dem geschätzten Aufwand) eines Algorithmus ist der lineare Teil gegenüber dem quadratischen zu vernachlässigen, da uns hier nur interessiert, wie sich der Algorithmus bei großen Datenmengen, also großen "max" verhält.
Folglich hat der Algorithmus quadratische Komplexität: t ~ max².
Die "zentrale Anweisung" ist ja der Vergleich feld[j] > feld[j+1].
Also schauen wir uns einfach mal an, wie oft diese ausgeführt wird (den Algorithmus einfach mal im Kopf durchgehen):
max=1 --> 1-mal
max=2 --> (2+1) mal
max=3 --> (3+2+1) mal
max=4 --> (4+3+2+1) mal
allgemein: 1+2+3+...+max mal
Nach der gaußschen Summenformel gilt:
1+2+3+...+max = ( max*(max+1) ) / 2
=(max²+max)/2
Bei der Komplexität (dem geschätzten Aufwand) eines Algorithmus ist der lineare Teil gegenüber dem quadratischen zu vernachlässigen, da uns hier nur interessiert, wie sich der Algorithmus bei großen Datenmengen, also großen "max" verhält.
Folglich hat der Algorithmus quadratische Komplexität: t ~ max².