sciencetalk

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 () 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).
Dank bij voorbaat,

Roger

Wat betekent T(n) ?

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

Beide oefeningen gaan op dezelfde manier.

Vraag jezelf het volgende af: hoe vaak wordt de buitenste lus uitgevoerd?

Volgens mij wordt die 'k' keer uitgevoerd.

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.

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

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.

Dus = j + 1 - 1 = j.

Dan krijgen we: = 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.

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?

Ik denk dat je het volgende bedoelt:

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

Ben je bekend met meetkundige rijen?

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

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

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.