• Ad Laufzeiten:


    a)
    x--
    ?
    x--
    x--



    das zweite fand ich etwas kompliziert ohne taschenrechner, daher hab ich geschummelt und da kommt auch raus, dass es gegen 0 geht, also
    x--


    kann das sein?


    b) bei den beweisen hab ich so meine probleme, kann das jemand versuchen?


    ich dachte mir das beim ersten so: annahme : bedingung wahr
    f(n) = O (g(n)) ==> f(n) = O( 2g(n) + log2g(n))
    1) f(n) = O(g(n))
    2) f(n) = O( 2g(n) + log2g(n))


    ad1) Es gibt c1, n0 > 0 | für alle n >= n0 : 0 <= f(n) <= c1 * g(n)
    ad2 ) Es gibt c2, n0 > 0 | für alle n >= n0 : 0 <= f(n) <= c2 * (2g(n) + log2g(n))


    dann dachte ich mir:
    log2g(n) kann man weglassen, da es kleiner als g(n) ist und somit für die grenzwerte keine rolle spielt, denn wenn g(n) eine obere Schranke von f(n) ist, ist auch g(n) + logn eine obere schranke von f(n). daher lasse ich den log weg.
    dann habe ich noch stehen
    1) 0 <= f(n) <= c1 * g(n)
    2) 0 <= f(n) <= c2 * 2g(n)


    Die zweite Bedingung ist dann wahr, wenn die erste wahr ist und c1 = 2*c oder c2 = c/2.
    Behauptung ist somit wahr.



    c) n² logn ; n logn



    2:
    b)
    quicksort ist nicht stabil, ist aber beste verfahren in der praxis. den worst case kann man dadurch umgehen, dass man das pivotelement zufällig wählt oder das erste, mittlere und letzte element miteinander vergleicht und dann das mittlere davon nimmt. somit kein WC von n²


    c) ?

  • hmm.. welchen test meinst du? finde keinen vom 9.3.2003... nur einen für 9.4.2003.. und da gibs kein c..

    When I was a little kid my mother told me not to stare into the sun. So once when I was six, I did. The doctors didn't know if my eyes would ever heal. I was terrified, alone in that darkness. Slowly daylight crept in through the bandages, and I could see, but something else had changed inside of me. That day I had my first headache.
    __________________________
    what do you mean "freak"?

  • Zitat von .coma.

    hmm.. welchen test meinst du? finde keinen vom 9.3.2003... nur einen für 9.4.2003.. und da gibs kein c..


    http://www.ads.tuwien.ac.at/teaching/LVA/184172.html


    ganz unten gibts Beurteilung und dort gibts nochmal zum üben tests :)


    in meinem fall hab ich 09.05.2003 genommen und mich leider im threadtitel verschrieben, mal schaun ob ich das ändern kann..

  • Zitat von Venefica

    in meinem fall hab ich 09.05.2003 genommen und mich leider im threadtitel verschrieben, mal schaun ob ich das ändern kann..


    So wie es ausschaut, die ansonsten so großartige Eigenschaft dieses Forums, nämlich dass die Antworten so rasch kommen ist in diesem Fall zugleich ein winziger Nachteil, da nur die Titel von unbeantworteten Posts können von den normalen Threadstarter User geändert werden. :shinner:

  • Zitat von bnd

    So wie es ausschaut, die ansonsten so großartige Eigenschaft dieses Forums, nämlich dass die Antworten so rasch kommen ist in diesem Fall zugleich ein winziger Nachteil, da nur die Titel von unbeantworteten Posts können von den normalen Threadstarter User geändert werden. :shinner:


    hab ich leider auch schon bemerkt ;(