Laufzeitabschätzung
Results 1 to 9 of 9
  1. #1

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Laufzeitabschätzung

    Hallo! Schreib am Fr die Prüfung und sind noch einige Fragen offen.
    Ein beliebtes Prüfungsbeispiel ist das Abschätzen von Laufzeiten (Bewerten von kleinen Codestücken). Gibts dafür irgendein Rezept? Ganz vestehe ich das nicht wie ich genau das sehen soll, ob die Laufzeit in n, n² oder n log n ist (oder ähnliches)?

    thx for help

  2. #2
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    naja, im prinzip schaust du dir das programm an und überlegst, wie oft eine programmzeile in abhängigkeit von der Anzahl n der Eingabeelemente ausgeführt wird.
    wenn sich z.B. bei verdoppelter Anzahl der Elemente die Anzahl der Durchläufe (ist im code meist zeilen- bzw. blockweise zu sehen) verdoppelt, dann hast du Theta(n),
    wenn die Durchläufe sich vervierfachen, hast du Theta(n²).
    Bei irgendwelchen rekursiven "Teile und Herrsche"-Algorithmen ists meistens Theta(n*logn)

    hoff das hilft.
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  3. #3

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    also gibt es da kein allgemeines Rezept wie: for-Schleife -> n², while-Schleife n log n , usw....?

  4. #4
    Irrlicht's Avatar
    Title
    Hero
    Join Date
    Feb 2002
    Location
    Wien
    Posts
    208
    Thanks
    0
    Thanked 1 Time in 1 Post
    eine while-schleife ist nicht viel anderes als eine for-schleife.
    Also: nö.

  5. #5
    eXe's Avatar
    Title
    Principal
    Join Date
    Feb 2002
    Posts
    99
    Thanks
    0
    Thanked 0 Times in 0 Posts
    naja wenns zwei verschachtelte schleifen sind kanns scho mal nimma linear sein - oder?

  6. #6
    steve's Avatar
    Title
    Baccalaureus
    Join Date
    Jan 2002
    Location
    planet earth
    Posts
    539
    Thanks
    14
    Thanked 2 Times in 2 Posts
    nein, mit der art der schleife hats überhaupt nichts zu tun. du musst dir nur übelegen, wie oft eine zeile ausgeführt wird.

    Wie eXe schon vermutet hat, deutet eine verschachtelte schleife schon auf nicht-linearität hin. (zum weiteren verwirren: wobei hier in beiden schleifen irgendwie ein n vorkommen muss als bedingung oder so, oder sich zumindest in beiden was verändern muss mit geändertem n, denn sonst ists wieder nur linear )
    -----BEGIN GEEK CODE BLOCK-----
    Version: 3.12
    GAT d-(+) s++: a- C++$>+$ U++>+++ P++>+++ L+++ !E W++>$ !N K? w(--)@ !O !M V? PS+ PE++(-)> Y+ PGP(+) t---(-) !5 X R- tv-(--) b++>$ DI+ D+(++) G(+) e>++++* h-- r++ y++
    ------END GEEK CODE BLOCK------ .

  7. #7

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Kann mir hier wer bitte die Lösung geben, wenn geht mit kurzer Erklärung

    Laufzeiten in Theta-Notation
    --------------------------------------------------------------------

    A.)
    l = n+10;
    while (l>0) {
    k = n*n-1;
    l = l-1;
    }

    B.)
    while (n>0) {
    n=n-1234;
    k=n+n*n;
    }

    C.)
    k=n;
    while (k>1) {
    k=k/2;
    l=n*k;
    }

    D.) Die Funktion Dummy wird mit Argument hn aufgerufen, und ist wie folgt definiert:

    Function Dummy(k);
    For (i=1,...,k) {
    l=l+1;
    }
    m=floor(K/2);
    if (m>0) Dummy(m);

    floor rundet auf die nächste ganze Zahl ab.
    -------------------------------------------------------------
    Für mich ist das Problem, dass ich keine gelösten Sachen dieser Art habe (ausser das Insertion Sort Bsp. ausm Skript), demnach hab ich auch nix zum nachvollziehen, desewegen wärs super, wenn mir hier wär die Lösung zukommen lassen würde.

    P.S: Im AlgoDat BUch von "Ottmann, Widmayer" steht zu den Laufzeiten so gut wie gar nix drin. Der Rest unseres Skriptums ist aber 1 zu 1 aus diesem Buch rausgenommen.

  8. #8
    fraka79
    hy mrfloppy

    hab hier die lsg.
    für deine 4 programmstückchen

    hoff sie helfen dir
    lg fraka
    Attached Images Attached Images  

  9. #9

    Title
    Veteran
    Join Date
    May 2002
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    THX! Genau das hab ich gebraucht. Hilft mir extrem weiter. Danke nochmal!

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •