Cooler Adblocker Abiunity kannst du auch ohne Adblocker werbefrei nutzen ;) Einfach registrieren und mehr als 10 Bedankungen sammeln!
 
Chrisrock
Schüler | Niedersachsen
26.10.2010 um 17:35 Uhr
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
0
#104135
Melde dich an oder registriere dich, um zu kommentieren. AnmeldenRegistrieren
 
EddaE
Schüler | Niedersachsen
26.10.2010 um 19:27 Uhr
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???
0
#104171
 
sontes92
Schüler | Niedersachsen
28.10.2010 um 21:23 Uhr
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?
0
#104435
 
blra
Schüler | Niedersachsen
01.11.2010 um 15:49 Uhr
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).
0
#104850
 
0x3E9
Schüler | Niedersachsen
01.11.2010 um 22:35 Uhr
@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².
0
#104959
Cooler Adblocker Abiunity kannst du auch ohne Adblocker werbefrei nutzen ;) Einfach registrieren und mehr als 10 Bedankungen sammeln!
x
BBCodes