[FRAGE] - Laufzeit berechnen
Results 1 to 5 of 5
  1. #1

    Title
    Dipl.Ing
    Join Date
    May 2002
    Posts
    1,074
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Red face Laufzeit berechnen

    Hi,

    ich hätte da eine Frage. Bei dem 3 Bsp. muss man ja die Laufzeit berechnen. Was heisst ich brauch auch den Faktor. (n; n-1;...)

    Wie komm ich auf das. Ich versteh das überhaupt nicht. Vielleicht könnte mir das jemand erklären. Ich habe nämlich bei der letzten Vorlesung gefehlt. Vielleicht fehlt mir deshalb der Durchblick.

    Von wegen Theta,...???


    mfg crow

  2. #2
    Judas42's Avatar
    Title
    Elite
    Join Date
    Jul 2002
    Location
    Wien
    Posts
    360
    Thanks
    0
    Thanked 1 Time in 1 Post
    würd mich auch interessieren... hab schon etwas herumgetüftelt und bin jetzt kurz davor, den algorithmus mal zu coden und die laufzeit im debugger zu analysieren...
    "The letters are Hex, of an ancient mode, but the language is that of Microsoft, which I shall not utter here."

  3. #3

    Title
    Dipl.Ing
    Join Date
    May 2002
    Posts
    1,074
    Thanks
    0
    Thanked 0 Times in 0 Posts
    HI,

    ich hab mir heute das Skript zugelegt und es hat mir tatsächlich geholfen. Leider habe ich immer noch keine Ahnung wie man die Laufzeit von einem Algorithmus berechnet. In der Vorlesung hat er das ja auch nicht wirklich erklärt.

    Da morgen schon die Übung ist, wäre ich über Hilfe sehr dankbar.


    mfg crow

  4. #4

    Title
    Principal
    Join Date
    May 2002
    Location
    wien 12
    Posts
    86
    Thanks
    0
    Thanked 0 Times in 0 Posts

    bsp 3

    hi, also ich hab mir folgendes gedacht :
    a)

    t = n; ....wird einmal durchlaufen

    wiederhole

    k=n^5 - t; .... n/3
    t=t - 3; .... n/3

    bis t<=0 .... n/3

    d.h. deta 1 + 3 * (n/3) = deta (n) ... da ja keine höhere potenz als n entsteht ......????

    b)

    m = n ....einmal
    solange m > 0 ...... n/2 + 1 mal wenn man nachrechnet
    {
    für i= 1 .... m+26 ... n/2 +26
    {
    j=j+1; ... ....n/2 + 25
    }
    m=m/2 => abgerundet ... n/2
    }

    d.h. deta (1) + (n/2 + 1) + [(n/2+26)*n/2] + [(n/2 + 25)*n/2] + [(n/2)*n/2]

    => deta n^2 ........???????

    wär cool wenn noch wer returschreibt

  5. #5

    Title
    Dipl.Ing
    Join Date
    Mar 2002
    Location
    Wien 12
    Posts
    1,135
    Thanks
    72
    Thanked 366 Times in 208 Posts
    ad a)
    > deta (n) ... da ja keine höhere potenz als n entsteht

    Ja, so erkennt man manchmal recht schnell die Komplexitaet.

    Bei diesem Beispiel wuerde ich auch \Theta(n) sagen.

    ad b)
    Die Zeile "m > 0 ..." wird nicht (n/2 + 1)-mal sondern (ld(n) + 2)-mal abgearbeitet (ld(x) := ln(x)/ln(2), der logarithmus dualis von x).

    Zum Beispiel fuer n = 10. Laut deiner Formel muesste diese Zeile 6 mal erreicht werden. Sie wird aber nur 5 mal erreicht ([ld(10)] = 3):

    10 > 0 ...ok
    5 > 0 ...ok
    2 > 0 ...ok
    1 > 0 ...ok
    0 > 0 ...abbruch

    Ich bin der Meinung die Laufzeit ist in \Theta(n log n). Denn die innere Schleife ist linear und wird im ganzen (ld(n) + 2)-mal ausgefuehrt. Da gibt es aber auch noch einen anderen Ansatz in diesem Thread.

    /edit 18.10.02:
    Nein, es ist in \Theta(n). Tja man sollte eben nicht immer die Musterloesungen glauben ;-). Der andere Ansatz stimmt.
    Last edited by yrucrem; 18-10-2002 at 20:42.

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
  •