UE-Test

  • Jimmy : stimmt selection sort is instabil. hab das vertauschen vergessen.
    (Allerdings sobald man eine verketterte Liste statt array verwendet kann man statt vertauschen nur einfügen - dann würde das prinzip von selection sort erhalten bleibe und stabil wärs auch. also möglich müssts schon sein)



    Lukas : der 2. Merge Sort (Seite 35) is der instabile.
    weil die rechte hälfte in umgekehrter reihenfolge gespeichert wird
    und dann immmre das linke element falls gleich übernommen wird
    (einfach mit vier gleichen zahlen ausprobieren)

  • bsp:


    f(n) = theta wurzel ( f( n²) ) ?




    und wegen den rekursiven, wie schauts mit sowas aus :


    NONAME (p,q)


    aufruf von noname(1,n):


    falls p<q
    l = floor (p+q/2;
    noname (p,1)
    noname (l+1, q);
    for i=p....q {
    print i;}



    wie bestimmt ma die laufzeit von rekusriven algorithmen, zb diesem hier ?

  • Zitat

    Original geschrieben von Shade
    wenn wir schon bei laufzeiten sind:
    müssen wir die auch herleiten können,oder reicht es wenn wir die auswendig können?


    Denke mal, dass auch das Teil des Tests sein kann, denn in den Übungsbsp. waren auch solche vorhanden.

  • hmm,das stimmt.aber ich hab hauptsächlich deshalb gefragt ,weil die herleitung von der laufzeit für rekursive algorythmen recht schwer ist.
    wurde beim repititorium nicht gesagt ob man das können muss?