Results 1 to 5 of 5

Thread: 09.03.2003

  1. #1
    Venefica's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Posts
    1,075
    Thanks Thanks Given 
    74
    Thanks Thanks Received 
    146
    Thanked in
    76 Posts

    09.05.2003

    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) ?
    Last edited by Venefica; 17-11-2005 at 18:34.
    manamana düdüdüdüdü

  2. #2
    .coma.'s Avatar
    Title
    Elite
    Join Date
    Mar 2005
    Posts
    387
    Thanks Thanks Given 
    8
    Thanks Thanks Received 
    3
    Thanked in
    3 Posts
    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"?

  3. #3
    Venefica's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Posts
    1,075
    Thanks Thanks Given 
    74
    Thanks Thanks Received 
    146
    Thanked in
    76 Posts
    Quote Originally Posted by .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..
    manamana düdüdüdüdü

  4. #4

    Title
    Principal
    Join Date
    Nov 2002
    Posts
    95
    Thanks Thanks Given 
    2
    Thanks Thanks Received 
    0
    Thanked in
    0 Posts
    Quote Originally Posted by 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.
    The mainframes are dead, long live the mainframes!
    http://jedi.informatik.uni-leipzig.de/index.html


  5. #5
    Venefica's Avatar
    Title
    Dipl.Ing
    Join Date
    Oct 2003
    Posts
    1,075
    Thanks Thanks Given 
    74
    Thanks Thanks Received 
    146
    Thanked in
    76 Posts
    Quote Originally Posted by 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.
    hab ich leider auch schon bemerkt ;(
    manamana düdüdüdüdü

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
  •