Moderators: dirkwb, Xilvo
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de
Huiswerkbijsluiter
-
- Berichten: 122
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 (
\(\sum \)
) 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 (22.29 KiB) 757 keer bekeken
Dank bij voorbaat,
Roger
-
- Berichten: 2.906
Wat betekent T(n) ?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 122
We noteren voor een inputgrootte n de uitvoeringstijd T van het algoritme als een functie van n, dus als T(n).
-
- Berichten: 2.906
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(); }
-
- Berichten: 122
Volgens mij wordt die 'k' keer uitgevoerd.
-
- Berichten: 2.906
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.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 122
Ik denk dat dit zou moeten kloppen:
\(\sum_{i=1}^{k}\sum_{i=1}^{j}1\)
Waarbij
\(\sum_{i=1}^{k}\)
we hier die while lus beschrijven.
-
- Berichten: 2.906
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(); }
-
- Berichten: 122
Dus
\(\sum_{i=1}^{j}\)
= j + 1 - 1 = j.
Dan krijgen we:
\(\sum_{a=1}^{k} j\)
= 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.
-
- Berichten: 2.906
Energyfellow schreef: ↑wo 03 apr 2013, 14:05
Dan krijgen we:
\(\sum_{m=1}^{k} j\)
= 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(); }
-
- Berichten: 122
Ik denk dat je het volgende bedoelt:
\(\sum_{i=1}^{k}3^{i}\)
-
- Berichten: 2.906
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..
Energyfellow schreef: ↑wo 03 apr 2013, 14:22
Ik denk dat je het volgende bedoelt:
\(\sum_{i=1}^{k}3^{i}\)
inderdaad
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 2.906
Ben je bekend met meetkundige rijen?
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
-
- Berichten: 122
Nee, maar wat niet is ik kan komen hé
.
Maar voor de tweede heb ik wel een een logaritmische tijdeenheid hé.
-
- Berichten: 2.906
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.org/wiki/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(); }
