Algoritmen T(n) berekenen while lus

[Energyfellow]

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 831 keer bekeken

Dank bij voorbaat,

Roger

[Math-E-Mad-X]

Wat betekent T(n) ?

[Energyfellow]

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

[Math-E-Mad-X]

Beide oefeningen gaan op dezelfde manier.

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

[Energyfellow]

Volgens mij wordt die 'k' keer uitgevoerd.

[Math-E-Mad-X]

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.

[Energyfellow]

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.

[Math-E-Mad-X]

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.

[Energyfellow]

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.

[Math-E-Mad-X]

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?

[Energyfellow]

Ik denk dat je het volgende bedoelt:

\(\sum_{i=1}^{k}3^{i}\)

[Math-E-Mad-X]

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:

\(\sum_{i=1}^{k}3^{i}\)

inderdaad

[Math-E-Mad-X]

Ben je bekend met meetkundige rijen?

[Energyfellow]

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

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

[Math-E-Mad-X]

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.