Übungsblatt 1

  • Beispiel 7:


    111, 11, 1, 1, 110, 111, 1


    Erstelle Heap()
    111|110,111| 1, 11, 1, 1


    111|110,1|1,11,1, |111
    110|11,1|1,1,1, |111, 111
    11|1,1|1 |110, 111, 111
    1|1,1| |11, 110, 111, 111
    1|1 |1, 11, 110, 111, 111
    1 |1, 11, 110, 111, 111



    Beispiel 8:


    Algorithmus umändern auf: falls A[i].key > A[maxpos].key dann {...


    <13,9,10,6,3,5,8,9>
    <13|10,9,6,3,5,8,9>
    <13,10|9,6,3,5,8,9>
    <13,10,9|9,3,5,8,6>
    <13,10,9,9|8,5,3,6>
    <13,10,9,9,8|6,3,5>
    <13,10,9,9,8,6|5,3>


    Was sagt ihr dazu?

  • Hallo


    Hat in der Vorbesprechung nicht viel gemacht. Nur Selection Sort, Insertion Sort und eine kurze Einführung zur Analyse von Algorithmen. Wären nur die ersten drei Seien im Skriptum.


    LG

  • Hab gerade mit Aufgabe 5b) angefangen, momentan komm ich nicht wirklich weiter.


    f(n) = Theta(g(n)) ⇒ g(n) = Theta(f(n))


    Dann hab ich für den linken Teil die Definition verwendet und eingesetzt:


    c1 * g(n) =< f(n) =< c2 * g(n) | durch g(n) dividieren
    c1 =< f(n) / g(n) =< c2


    Analog dasselbe für g(n) in Theta von f(n), also


    c3 =< g(n) / f(n) =< c4


    Also:


    c1 =< f(n) / g(n) =< c2 ==> c3 =< g(n) / f(n) =< c4


    Ist das der falsche Ansatz oder bin ich am richtigen Weg?



  • ich bin mir zwar nicht sicher, ob das stimmt, aber ich hab a) so gemacht:





    EDIT: das ist mit ziemlicher sicherheit doch bloedsinn, da die angabe ja nicht

    lautet..


    beim zweiten weiß ich's noch nicht genau


  • Fast ;)
    schau mal was passiert, wenn du anstatt durch f(n)g(n) dividierst und dann den Kehrwert nimmst...
    --chris

    hi, i'm a signature virus. copy me into your signature to help me spread.

  • Macht bitte fuer jedes Uebungsbeispiel einen eigenen Thread auf, wenn eine weile dahindiskutiert wird, wird das sonst schnell ziemlich unuebersichtlich.

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