Algoritmen Orde van toename

[Energyfellow]

Hey,

Ik snap niet goed hoe ik mijn T(n) moet bereken van onderstaand algoritme.

Code: Selecteer alles

Som:= 0

VOOR j:= 1 TOT n

   VOOR i:= 1 TOT j

  Som := som + …

   EINDE-VOR

EINDE-VOOR

VOOR k := 1 TOT n

   Som := som + k

EINDE-VOOR

De uitkomst is T(n) =

\(c1 + (c3 + 2)n + \frac{c2}{2}(n^2 + n)\)

, ik begrijp echter niet goed hoe men aan deze uitkomst komt.

Zou iemand mij kunnen helpen met dit stap voor stap op te lossen?

Dank bij voorbaat,

Roger

[Xenion]

Het lastige zijn waarschijnlijk die lussen:

Laten we beginnen met de onderste loop: je voert die uit voor k = 1 tot n. Je voert dus n keer uit wat daar binnen in staat. Je krijg een term in n.

De bovenste loop met die geneste loop binnenin:

Hier helpt het om eens stap voor stap te kijken wat er gebeurt.

Voor j = 1 voer je de binnenste loop 1 keer uit.

Voor j = 2 voer je de binnenste loop 2 keer uit.

...

Voor j = n voer je de binnenste loop n keer uit.

In totaal heb je de binnenste loop dus 1+2+...+n keer uitgevoerd. Hier zou je een rij in moeten herkennen: simpelweg de rij met

\(a_i = i\)

. Je hebt normaal ooit wel eens geleerd hoe je de partieelsom van zo'n rij kan berekenen. Bereken dus

\(\sum_{i = 1}^n i\)

(hint).

Is het zo duidelijk?

[Energyfellow]

Hey,

Ik heb getracht het hieronder zo goed mogelijk uit te werken doch kom ik niet aan de modeloplossing.

Om te beginnen met de som := 0, die is constant en daar zullen we c1 aan toekennen.

We gaan ervan uit dat de som van de geneste loop constant is (c2) en met de formule die je gaf blijkt inderdaad dat die geneste lussen neerkomen op

\( \frac{1}{2}n * (n+1) \)

.

Bij de laatste lus gaan we er ook vanuit dat de som := ... daar constant is (c3), we voeren die lus daar n keer uit dus zouden we c3* n moeten krijgen.

Alles tesamen geeft dit mij: c1 + c3*n +

\( \frac{1}{2}c2 * (n * (n+1)) \)

.

Roger

[Xenion]

Je hebt dus 2n te weinig in vergelijking met de gegeven oplossing.

Hier ben ik niet zeker van maar kan het zijn dat die kost komt omdat je 2 keer een loop van 1 tot n doet? Dat loopen zelf kost ook nog enige tijd, onafhankelijk van wat er in de loop zelf nog gebeurt. (De kost van die loop van 1 tot j zit dan al bij in de kost c2.)

[Math-E-Mad-X]

Ik vind de oplossing die erbij gegeven is erg raar. Immers, wat heeft het voor zin om een constante c3 te definieren als je daar vervolgens 2 bij op gaat tellen? Dan kun je toch net zo goed gewoon een constante c4 definieren die gelijk is aan c3+2 ?

Tenzij ergens bij de opgave expliciet gegeven is wat c3 betekent.

[Xenion]

c3 staat volgens mij voor de kost van het stukje "Som := som + k". Zoals ik hierboven zeg vermoed ik dat er nog een kost 2n bijkomt voor het uitvoeren van die loops van 1 tot n. Conceptueel houdt het wel steek om dat dan niet bij in die c3 te stoppen.

Opmerking moderator

Ik verplaats dit topic overigens ook even naar 'Programmeren'.

[Energyfellow]

Dave,

Het is wel degelijk de juiste oplossing.



Mvg,

Roger

Ik heb wel nog een vraagje. Ik ondervind dat ik het volledig uitwerken van zulke partiële sommen nog niet volledig onder de knie heb.



Hoe begin ik eraan om dit op te lossen?

Dank bij voorbaat,

Roger

[Xenion]

Mja die 2n kan ik niet verklaren. Voor je andere vraag: zie je ander topic.

[Math-E-Mad-X]

c3 staat volgens mij voor de kost van het stukje "Som := som + k". Zoals ik hierboven zeg vermoed ik dat er nog een kost 2n bijkomt voor het uitvoeren van die loops van 1 tot n. Conceptueel houdt het wel steek om dat dan niet bij in die c3 te stoppen.

Maar dan zou je dat ook moeten doen voor die dubbele loop, dus dan zou er ook nog een extra term n^2 bij moeten komen..

Trouwens, wat ik ook vreemd vind is dat die pseudo-code in het Nederlands is. Dat heb ik echt nog nooit gezien. Geeft me het gevoel dat de schrijver van de opgave niet echt professioneel is.

[Xenion]

Ik denk dat je best eens aan je leerkracht vraagt hoe het precies zit.

Trouwens, wat ik ook vreemd vind is dat die pseudo-code in het Nederlands is. Dat heb ik echt nog nooit gezien. Geeft me het gevoel dat de schrijver van de opgave niet echt professioneel is.

Ik heb het zelf in het middelbaar ook ooit zo gezien Maar sinds dan inderdaad nooit meer.