[A&C]

Forum van 2de Bachelor Informatica.

Moderator: Praesidium

User avatar
Fristi
WOZ
Posts: 4565

[A&C]

Post#1 » Sun Jun 14, 2009 9:23 pm

Loha

Wederom een vraagje, deze keer eentje uit den tuyeaux.

een van de eerste voorbeelden is:

Code: Select all

function nestedloops(int m, n) {
int i=1;
int j = 1;
while (i <= m) {
while (j <= n) {
j = j+1;
}
i = i + 1;
}
}
Dan moet men hier de complexiteit van nemen en dan vraagt men hierna om max. 2 regels aan te passen zodat de complexiteit O(m * log n) wordt.

a) is de complexiteit van dit stuk code O(m+n)?
b) wat moet er net aangepast worden?

Greets
Fristi
Fristi Ad Infinitum

WINAK WOZ 2013 - ...
WINAK Magister Fristi 2012-2013
WINAK Feest 2011-2012
WINAK Schachtentemmer 2010-2011
WINAK Scriptor 2008-2009 | 2009-2010

Pieter Belmans
Posts: 593
Contact:

Post#2 » Sun Jun 14, 2009 9:34 pm

De complexiteit is O(m+n), tenzij ik er mijlenver naast zit.

Truuk is om bij elke iteratie van uw buitenste lus iets log n achtigs te doen. Ge verplaatst de assignment/declaratie (C++ mierenneukers, ga uw gang!) binnen die eerste lus, en ge vermenigvuldigt j telkens met 2 (of een ander willekeurig getal groter dan 1).

Nu zal ne goeie compiler heel die functie gewoon wegoptimaliseren, aangezien ge toch niks zinnigs doet. Maar Compilers is pas voor 1e master vrees ik :P.

User avatar
zarry
Posts: 212

Post#3 » Sun Jun 14, 2009 9:36 pm

volgens mij is het ook O(m+n) ja..

Code: Select all


function nestedloops(int m, n) { 
int i=1;
int j = 1;
while (i <= m) {
j = 1;
while (j <= n) {
j = 2*j;
}
i = i + 1;
}
}
zoiets?
Ik spreek Zwarryzwaniaans en jij?

Pieter Belmans
Posts: 593
Contact:

Post#4 » Sun Jun 14, 2009 9:45 pm

Jup, that should do the trick.

User avatar
Fristi
WOZ
Posts: 4565

Post#5 » Sun Jun 14, 2009 10:02 pm

wow, ik had het zowaar just, kewl

thanks for the answer
Fristi Ad Infinitum

WINAK WOZ 2013 - ...
WINAK Magister Fristi 2012-2013
WINAK Feest 2011-2012
WINAK Schachtentemmer 2010-2011
WINAK Scriptor 2008-2009 | 2009-2010

User avatar
racekakje
WOZ
Posts: 740

Post#6 » Sun Jun 14, 2009 10:34 pm

Waarom complexiteit O(m+n) en niet O(m * n)?
Ge hebt toch een geneste lus..

Is

Code: Select all


function nestedloops(int m, n) {
int i=1;
int j = 1;
while (i <= m + n) {
i = i + 1;
}
}
niet O(m+n)?


Met de oplossing voor O(m*logn) te krijgen ben ik akkoord..

Pieter Belmans
Posts: 593
Contact:

Post#7 » Sun Jun 14, 2009 10:39 pm

1 keer de binnenste lus doorlopen en j == n voor de rest van de uitvoering. O(n+m) it is dus.

User avatar
zarry
Posts: 212

Post#8 » Mon Jun 15, 2009 4:50 pm

op p102 in de cursus staat er zo bij elk puntje de lengte.. kan er iemand zo kort uitlegge vanwaar da komt? tnx
Ik spreek Zwarryzwaniaans en jij?

Pieter Belmans
Posts: 593
Contact:

Post#9 » Mon Jun 15, 2009 7:23 pm

De uitdrukking heeft lengte . Kijk dus bij elke uitdrukking wanneer ge iets van lengte invult in die uitdrukking en wanneer ge een conjunctie neemt van zo'n uitdrukkingen. Alles wat niet iets over valt weg als constante factor.

Return to “2de Bachelor”

Who is online

Users browsing this forum: No registered users and 2 guests

cron