Springen naar inhoud

Algoritmen T(n) berekenen while lus


  • Log in om te kunnen reageren

#1

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 31 maart 2013 - 23:18

Hallo,

Ik heb na lang zoeken het min of meer onder de knie gekregen hoe ik een for lus in pseudocode uit een algoritme moet omzetten naar een som (LaTeX ) en hieruit dan de Thèta n (T(n)) berekenen.

Maar ik worstel nu met het volgende: hoe doe ik dit met while lus?
Kan er mij iemand helpen hij het oplossen van onderstaande twee oefeningen?
Opdracht: bereken T(n).

While.PNG

Dank bij voorbaat,
Roger

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 02 april 2013 - 13:25

Wat betekent T(n) ?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#3

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 02 april 2013 - 14:48

We noteren voor een inputgrootte n de uitvoeringstijd T van het algoritme als een functie van n, dus als T(n).

#4

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 10:20

Beide oefeningen gaan op dezelfde manier.

Vraag jezelf het volgende af: hoe vaak wordt de buitenste lus uitgevoerd?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#5

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 12:44

Volgens mij wordt die 'k' keer uitgevoerd.

#6

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 12:48

Klopt.

De binnenste lus wordt duidelijk j keer uitgevoerd. Je krijgt dus twee sommaties, één met een index die loopt van 1 tot k en één die loopt van 1 tot j.

Probeer dit eens uit te schrijven met sommatie tekens.

Veranderd door Math-E-Mad-X, 03 april 2013 - 12:55

while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#7

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 12:50

Ik denk dat dit zou moeten kloppen:
LaTeX
Waarbij LaTeX we hier die while lus beschrijven.

Veranderd door Energyfellow, 03 april 2013 - 12:50


#8

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:00

Klopt, al moet je bij die eerste sommatie van 1 tot k eigenlijk een andere index dan i gebruiken, bijvoorbeeld m.

Volgende stap: de sommatie van 1 tot j kun je gemakkelijk vereenvoudigen.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#9

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:05

Dus LaTeX = j + 1 - 1 = j.
Dan krijgen we: LaTeX = j * k waarbij j = n, dat geeft ons dan n * k.
Als we dat eens neerpennen met links n en rechts k:
1 3
2 9
3 27
= Log(n) k, we hebben hier dus een logaritmisch tijdverloop.

Veranderd door Energyfellow, 03 april 2013 - 13:06


#10

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:07

Dan krijgen we: LaTeX

= j * k

Hier ga je iets te kort door de bocht! j is namelijk afhankelijk van m!

hoe kun je j als functie van m schrijven?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#11

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:22

Ik denk dat je het volgende bedoelt: LaTeX

#12

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:26

Hint:
De eerste keer dat de buitenste lus wordt doorlopen hebben we m=1 en j=n
De tweede keer dat de buitenste lus wordt doorlopen hebben we m=2 en j=...
etc..

Ik denk dat je het volgende bedoelt: LaTeX


inderdaad
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#13

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:31

Ben je bekend met meetkundige rijen?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }

#14

Energyfellow

    Energyfellow


  • >100 berichten
  • 122 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:33

Nee, maar wat niet is ik kan komen hé ;) .

Maar voor de tweede heb ik wel een een logaritmische tijdeenheid hé.

Veranderd door Energyfellow, 03 april 2013 - 13:44


#15

Math-E-Mad-X

    Math-E-Mad-X


  • >1k berichten
  • 2383 berichten
  • Ervaren gebruiker

Geplaatst op 03 april 2013 - 13:41

Ah, ja, inderdaad, voor de tweede opgave klopt het wel wat je zei.

De sommatie bij de eerste opgave kun je verder uitwerken met:
http://nl.wikipedia....Meetkundige_rij

En de laatste stap is dan het uitschrijven van k als functie van n.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures