Blatt2 - Loesungen

  • Was passiert jetzt aber in dem Fall wenn es kein i gibt dass größer ist als x oder auch wenn es kein j gibt, dass kleiner ist ... wohin zeigt dann i???
    Vielleicht stehe ich auch nur auf der leitung ...

  • Iris :
    Das i muss kein Element finden das _groeszer_ ist, sondern eines, das _groeszer oder gleich_ ist als das Pivotelement. Und spaetestens, wenn es beim P-Element selbst ankommt hat es so ein Element gefunden. Dann wird eben das P-Element auf sich selbst verschoben.


    Das j bleibt spaetestens ganz am anfang des Feldes stehen wo ja ein Stop-Element plaziert wurde, dass kleiner ist als alle anderen Elemente im Feld.

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • jetzt müßte in zeile 8 auch noch <= stehen, denn laut buch:


    stoppelement A[0].key=kleine Zahl<= min (i=1 bis n) A[i].key


    wenn das stoppelement gleich ist mit dem minimum (pivotelement): endlosschleife

  • ok jetzt sollte das problem gelöst sein


    ich habs anhand folgendem beispiel probiert:
    2 2 4 2 2


    in zeile 8 kommt auch <=, denn sonst funktionierts nicht


    endgültig:
    - zeile 5 >=
    - zeile 8 <=
    - zeile 9 <
    - zeile 12 >

  • meiner meinung nach müsste die Laufzeit von zeile 4
    von bubblesort


    SUMME (i=1 bis (n^2-n)/2) von ti, ti element aus {0,1}


    so wie es im file steht mit SUMME (i=1 bis n-1), wäre ja nach
    einem durchlauf die folge schon sortiert.


    oder hab ich da einen denkfehler?
    lg, tocvolxa

  • andy :
    Stimmt, wenn man das Stop-Element kleiner oder gleich waehlt, dann braucht man ein <=. Wenn man eins nimmt, das kleiner ist reicht ein <. Aber ich denke, dass es vor allem wichtig ist, dass man verstanden hat, _warum_ eine dieser Aenderungen noetig ist (und das man die Aenderungen so vornimmt, dass der Tutor am moeglichst verwirrt ist :-)).


    josi :
    Dieser Einwand wurde schon gebracht. Es wird aber ausdruecklich nach der Laufzeit in abhaengigkeit von _n_ gefragt! Die hoechste Potenz von n in c1+(k+1)c2+k*c3 ist n^0 = 1 --> \Theta(1)


    tocvolxa :
    Stimmt! Grober Denkfehler von mir. Ich bin gerade dabei das zu korigieren.


    /edit:
    Hab's ausgebessert. Mein Denkfehler war folgender: es kann maximal (summe von i = 1 bis n - 1)(i)-mal sein, dass Vertauscht werden muss (das sind (n^2 - n)/2) und ich habe aus dem i einfach gleich das ti gemacht.


    Danke fuer den Hinweis!

    Damn, here I was, minding my own business, just enjoying my second amendment rights, and you people have to FREAK out on me!

  • aufgabe 7) + 8):


    also ich glaube daß dort die Summe von ti*c4 von 1 bis n-1 läuft,
    denn wenn sie von 1 bis (n^2-n)/2 laufen würde, würde schlimmstenfalls eine ordnung von theta(n^4) herauskommen und das stimmt sicherlich nicht

  • In der Zeile 4 gibt es n²-n/2 mal die Möglichkeit,dass ein Element wirklich verschoben wirst. Wenn du dir dir den Code der nächsten optimierten Aufgabe ansiehst, siehst du, dass die Zeile 3 und deshalb auch die Zeile 4 max. n²-n/2 mal ausgeführt werden kann. Daher musst du bis dorthin summieren.

  • Zitat

    Original geschrieben von laborg


    kurven parrallel? aehm welche kurven meinst du?


    naja, 3^5^n und 3^5^n+1 ;) mit n gegen unendlich


    mfg, -z0nk-

    zonked [zpnkt] - if someone is zonked or zonked out, they are not capable of doing anything because they are tired, drunk, or drugged; an informal word.

  • Ich will ja keinem die Freude verderben, aber:


    das Ganze sieht auf den ersten Blick aus wie Theta(1), weil die Wiederholung der Schleife ja von k abhängt und nicht von n.


    Aber ... wovon hängt denn nun n ab?
    Damit n größer werden kann, muss zuerst k gestiegen sein (Zeile 1). Somit hängt n also doch mit k zusammen, oder?


    Meiner Meinung nach ist
    k= ln(n) / ln(2)
    (was dem ld=logarithmus dualis entspricht, oder?).
    Somit bedeutet das, dass das Programm
    Theta( ln(n) ) als Laufzeit hat, oder? Verkalkulier ich mich da irgendwo? Ich bin für Anregungen offen...


    soweit, sogut,
    steve

    -----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------ .



  • also ich hatte heute ue und unser tutor/gruppenleiter/whatever hat nix gegen theta(1) gesagt ! .... immerhin ist ja die laufzeitnotation von n gefragt und nicht von k ...und da die schleife von 1 bis k läuft und nicht bis n, ist es nun mal theta(1) :thumb: