Notationen (21.6)
Results 1 to 5 of 5
  1. #1
    Kampi's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Location
    Elysium
    Posts
    2,162
    Thanks
    256
    Thanked 620 Times in 349 Posts

    Notationen (21.6)

    wäre nett, wenn jemand die lösungen zu diesen notationen (und möglicher weise eine erklärung wie man dazu kommt) posten könnte.
    hier die angaben:

    Geben Sie die Laufzeiten in Abhängigkeit von n in Theta Notation an!

    (i) p = n+10
    solange p>0 {
    k = n²- p
    p = p-1
    }

    (ii) k = n
    wiederhole
    k = k/3;
    l = n*k;
    bis k<=1

    (iii) m = n
    wiederhole
    für i = 1,....,15 {
    p = p+i;
    }
    m = [m/2]; //abrunden!
    bis m<=0

    (iv) m = n
    solange m>0 {
    für i = 1,....,m+3 {
    k = k +i;
    }
    m = [m/2]; //abrunden!
    }
    Willfähriges Mitglied des Fefe-Zeitbinder-Botnets und der Open Source Tea Party.

  2. #2
    wolk's Avatar
    Title
    Baccalaureus
    Join Date
    Jun 2002
    Posts
    986
    Thanks
    0
    Thanked 0 Times in 0 Posts
    i) theta(n), da die schleife n+10 mal durchlaufen wird

    ii) theta(log n), (k=n=100, 1x,k=33,2x, k=11,3x,k=3,4x usw -> logarithmisch (hab gelesen dass es egal ist ob durch 2 oder durch 3)

    iii) theta (log n), gleich wie oben, nur dass hier halt durch 2 dividiert wird; die innere schleife ist konstant, d.h. sie verändert sich bei steigendem n nicht -> keine auswirkung auf laufzeit

    iv) theta (n), da innere schleife zuerst n mal durchlaufen wird und dann n/2, n/4, n/8 -> zusammen 2n -> n

    ich hoffe mal das stimmt, da ich am freitag algodat prüfung antrete

    wenn nicht, bitte korrigieren

    mfg

  3. #3
    Kampi's Avatar
    Title
    Super Moderator
    Join Date
    Feb 2002
    Location
    Elysium
    Posts
    2,162
    Thanks
    256
    Thanked 620 Times in 349 Posts
    Original geschrieben von wolk

    iv) theta (n), da innere schleife zuerst n mal durchlaufen wird und dann n/2, n/4, n/8 -> zusammen 2n -> n

    ich hoffe mal das stimmt, da ich am freitag algodat prüfung antrete

    wenn nicht, bitte korrigieren

    mfg
    ich würd sagen die innere wird (n+3) mal durchlaufen. die äußere (log(n)+1) mal. das ergibt theta(n*log(n)). oder etwa nicht? was meinst/meint du/ihr?
    mfg. kampi
    Last edited by Kampi; 07-10-2002 at 14:52.
    Willfähriges Mitglied des Fefe-Zeitbinder-Botnets und der Open Source Tea Party.

  4. #4

    Title
    Principal
    Join Date
    Sep 2002
    Posts
    61
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Würde ich auch so machen, also theta(n*log(n))

    Gibts vielleicht jemanden, der sich vor Freitag zusammensetzen will?

    mfg KA.

  5. #5
    wolk's Avatar
    Title
    Baccalaureus
    Join Date
    Jun 2002
    Posts
    986
    Thanks
    0
    Thanked 0 Times in 0 Posts
    ja ich hätte interesse

    und trotzdem plädiere ich bei nr 4 auf log n

    die innere schleife wird nicht n+3 mal durchlaufen
    beim 1. mal n+3 mal
    beim 2. mal n/2 +3 mal
    beim 3. mal n/4 +3 mal

    summa summarum 2 n (wenn prof kaiser mit seinem mathe unterricht recht haben sollte)

    wenn freitag trotzdem wer mit mir diskutieren möchte und vielleicht dabei die letzten 4-5 prüfungen durchüben möchte : einfach melden

    mfg wolk

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
  •