Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Aufwandsabschätzung
Gehe zu Seite 1, 2  Weiter
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Aufwandsabschätzung
 
Autor Nachricht
m.stegeman
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.04.2007
Beiträge: 22

BeitragVerfasst am: 28 Apr 2008 - 12:58:46    Titel: Aufwandsabschätzung

hi ich hab für diesen algo:

void sortieren (int a[], int tief , int hoch ){
if(a[ tief ] > a[ hoch ]) {
int temp = a[ tief ];
a[ tief ] = a[ hoch ];
a[ hoch ] = temp ;
}
if (( tief + 1) >= hoch ) return ;
int drittel = ( hoch - tief + 1) / 3;
sortieren (a, tief , hoch - drittel );
sortieren (a, tief + drittel , hoch );
sortieren (a, tief , hoch - drittel );

diese rekursionsformel herausbekommen: t(n)=t(n-1)+2*(3^(n-2))
(n=anzahl der elemente im array...... t(n)=anzahl der vergleiche)

jetzt muss ich mit dem master-theorem t(n)=a*t(n/b)+f(n) den aufwand abschätzen. a=3 und b=1,5... aber wie bekomme ich das f(n) heraus?

danke für die hilfe
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 28 Apr 2008 - 13:04:33    Titel:

Ich bin doch ein bisschen verwundert, wie du aus deiner Rekursionsformel t(n)=t(n-1)+2*(3^(n-2)) die Parameter a=3 und b=1,5 aus dem Master-Theorem ableitest. Kannst du das mal erklären?
m.stegeman
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.04.2007
Beiträge: 22

BeitragVerfasst am: 28 Apr 2008 - 15:58:26    Titel:

keine ahnung, ich hab irgendwo gelesen dass die anzahl der teilprobleme, in die ein hauptproblem zerteilt wird "a" ist. und der faktor, um den das teilproblem kleiner ist als das hauptproblem ist b. also a=3 und b=1,5.... was würdest du denn da einsetzen
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 28 Apr 2008 - 16:09:50    Titel:

Auf deine Rekursionsformel ist das Mastertheorem garnicht anwendbar. Sie ist jedoch auch nicht richtig.

Du siehst, dass die Methode drei rekursive Aufrufe hat, in denen das Array nur noch zwei Drittel der Länge hat. Also muss deine Rekursionsformel in etwa so aussehen:

t(n) = 3*t(2n/3) + f(n)

Jetzt kannst du a und b ablesen: a=3 und b=3/2

Wobei du f(n) noch rausfinden musst. Ein flüchtiger Blick sagt mir: f(n) ist in O(1)
m.stegeman
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.04.2007
Beiträge: 22

BeitragVerfasst am: 28 Apr 2008 - 19:17:35    Titel:

und ob meine rekursionsformel richtig ist! aus dem algo kriegt man diese wertetabelle raus:
n ------1 ----2 -----3 -----4 ------5 ------6
t(n) ---2 ----2 -----8 ----26----- 80-----242

und darauf passt tw(n)=tw(n-1)+2*(3^n-2)) wunderbar!
und wie soll ich bitte f(n)=O(1) in die t(n)=3t(2n/3)+f(n) einbauen??
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 28 Apr 2008 - 20:13:14    Titel:

Zitat:
und ob meine rekursionsformel richtig ist! aus dem algo kriegt man diese wertetabelle raus:
n ------1 ----2 -----3 -----4 ------5 ------6
t(n) ---2 ----2 -----8 ----26----- 80-----242

und darauf passt tw(n)=tw(n-1)+2*(3^n-2)) wunderbar!


Und alle ungeraden Zahlen sind Primzahlen:

3 ist Primzahl, 5 ist Primzahl, 7 ist Primzahl, ...

Passt auch wunderbar!


Laut deiner Rekursionsformel, für deren Auflösung man nicht das Master-Theorem braucht sondern nur sukkzessive auflösen muss, kommt raus, dass der Sortieralgorithmus ein exponentielles Laufzeitverhalten im Bereich O(3^n) hat.

Benutzt man das Mastertheorem mit a=3, b=1.5 und f(n)=O(1) (was man ja nicht genauer wissen muss, da das Mastertheorem keine genauere Spezifikation von f(n) verlangt) erhält man ein Laufzeitverhalten von O(n^log_b(a)) was ungefähr O(n^2.7) ist.

Ich bleibe also bei meiner Aussage: Deine Rekursionsformel ist falsch.
m.stegeman
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.04.2007
Beiträge: 22

BeitragVerfasst am: 28 Apr 2008 - 20:33:06    Titel:

okay und woran siehst du dass f(n) element aus O(1) ist? bzw wie berechne ich das?
Armin Gibbs
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 06.02.2008
Beiträge: 992

BeitragVerfasst am: 28 Apr 2008 - 20:37:57    Titel:

Die untersten drei Zeilen Code

Code:
sortieren (a, tief , hoch - drittel );
sortieren (a, tief + drittel , hoch );
sortieren (a, tief , hoch - drittel );


sind in der Gleichung durch 3*t(2*n/3) abgedeckt. Damit fehlen noch die anderen Zeilen, deren Aufwand in f(n) steckt.

Code:
if(a[ tief ] > a[ hoch ]) {
int temp = a[ tief ];
a[ tief ] = a[ hoch ];
a[ hoch ] = temp ;
}
if (( tief + 1) >= hoch ) return ;
int drittel = ( hoch - tief + 1) / 3;


Hier wird jede Zeile genau einmal ausgeführt. Und die Anzahl der Zeilen ist natürlich unabhängig von n. Also muss der Restaufwand f(n) konstant und somit in O(1) sein.
Betrachtet man nur die Vergleiche, so käme f(n)=2 raus (die zwei if-Bedingungen). Aber so genau braucht man es wie gesagt garnicht.
m.stegeman
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.04.2007
Beiträge: 22

BeitragVerfasst am: 28 Apr 2008 - 20:44:38    Titel:

sorry aber für mich wird dieses hier:
Code:
 if(a[ tief ] > a[ hoch ]) {
int temp = a[ tief ];
a[ tief ] = a[ hoch ];
a[ hoch ] = temp ;
}
if (( tief + 1) >= hoch ) return ;
int drittel = ( hoch - tief + 1) / 3;

nicht nur einmal ausgeführt sondern öfters, denn je höher das n desto öfter läuft der doch da durch wegen der rekursion....[/code]
m.stegeman
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 21.04.2007
Beiträge: 22

BeitragVerfasst am: 28 Apr 2008 - 20:52:31    Titel:

ahh jetzt verstehe ich es. dankeschön Smile
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Aufwandsabschätzung
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Gehe zu Seite 1, 2  Weiter
Seite 1 von 2

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum