Algoritmen Orde van toename

Moderators: jkien, Xilvo

Reageer

Bericht 20-02-'13, 21:11

Energyfellow

Gebruikersavatar
Berichten: 122

Algoritmen Orde van toename

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
Omhoog

Bericht 20-02-'13, 21:44

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Algoritmen Orde van toename

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?
Omhoog

Bericht 20-02-'13, 22:31

Energyfellow

Gebruikersavatar
Berichten: 122

Re: Algoritmen Orde van toename

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
Omhoog

Bericht 20-02-'13, 22:40

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Algoritmen Orde van toename

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.)
Omhoog

Bericht 21-02-'13, 11:06

Math-E-Mad-X

Gebruikersavatar
Berichten: 2.906

Re: Algoritmen Orde van toename

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.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
Omhoog

Bericht 21-02-'13, 11:26

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Algoritmen Orde van toename

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'.
Omhoog

Bericht 21-02-'13, 23:05

Energyfellow

Gebruikersavatar
Berichten: 122

Re: Algoritmen Orde van toename

Dave,

Het is wel degelijk de juiste oplossing.

Afbeelding

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.

Afbeelding

Hoe begin ik eraan om dit op te lossen?

Dank bij voorbaat,

Roger
Omhoog

Bericht 22-02-'13, 00:43

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Algoritmen Orde van toename

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

Bericht 22-02-'13, 11:08

Math-E-Mad-X

Gebruikersavatar
Berichten: 2.906

Re: Algoritmen Orde van toename

Xenion schreef: ↑do 21 feb 2013, 11:26
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.
while(true){ Thread.sleep(60*1000/180); bang_bassdrum(); }
Omhoog

Bericht 22-02-'13, 11:20

Xenion

Gebruikersavatar
Berichten: 2.609

Re: Algoritmen Orde van toename

Ik denk dat je best eens aan je leerkracht vraagt hoe het precies zit.
Math-E-Mad-X schreef: ↑vr 22 feb 2013, 11:08
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 :P Maar sinds dan inderdaad nooit meer.
Omhoog
Reageer

Terug naar “Informatica en programmeren”