WINAK

Posted: **Sun Jun 14, 2009 9:23 pm**

Loha

Wederom een vraagje, deze keer eentje uit den tuyeaux.

een van de eerste voorbeelden is:

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

Posted: **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

.

Posted: **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?

Posted: **Sun Jun 14, 2009 9:45 pm**

Jup, that should do the trick.

Posted: **Sun Jun 14, 2009 10:02 pm**

wow, ik had het zowaar just, kewl

thanks for the answer

Posted: **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..

Posted: **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.

Posted: **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

Posted: **Mon Jun 15, 2009 7:23 pm**

De uitdrukking $U(x_1,\ldots,x_l)$ heeft lengte $O(l^2)$ . Kijk dus bij elke uitdrukking wanneer ge iets van lengte $p(n)$ invult in die uitdrukking en wanneer ge een conjunctie neemt van zo'n uitdrukkingen. Alles wat niet iets over $p(n)$ valt weg als constante factor.

WINAK

[A&C]

[A&C]