O(n^m) recursiv

[crs12decoder]

As avea nevoie de un exemplu de algoritm recursiv cu o complexitate de O(n^m).

Pentru iterativ se fac pur si simplu m for-uri pentru vectori cu n elemente.

[JIHAD]

ce ai incercat si unde ai ajuns?

[Birkoff]

Exemplu:

Se da un site cu o pagina X cu Y linkuri interne in ea.

Sa se faca o functie recursiva care sa citeasca si sa memoreze linkurile din pagina X dupa care sa parcurga recursiv fiecare link si sa le indexeze si pe celelalte pagini pana la final.

Sa se afiseze linkurile gasite in toate paginile site-ului (exclus linkuri externe acelui site)

[em]

Oare ceva de genul ar merge? Doar c? codul meu nu face ?i ceva CPU intensive.

cacat(m, n, N)
if(m = 0 & n = 0)
 return;
if(n = 0)
 return cacat(m - 1, N, N);
return cacat(m, n - 1, N);

N il tot trimit ca sa salvez N-ul initial

Daca apelez

cacat(3, 4, 4);

-> cacat(3, 3, 4)

-> cacat(3, 2, 4)

-> cacat(3, 1, 4)

-> cacat(3, 0, 4)

-> cacat(2, 3, 4)

-> cacat(2, 2, 4)

etc.

De fapt sunt putin confuz "pur si simplu m for-uri pentru vectori cu n elemente" -> Asta nu genereaza O(n*m)? Adica nu O(n^m)

Edited December 27, 2014 by em

[crs12decoder]

@em.

Functia cacat are complexitate n*m. In cazul de fata va avea 4*4 output-uri.

De fapt sunt putin confuz "pur si simplu m for-uri pentru vectori cu n elemente" -> Asta nu genereaza O(n*m)? Adica nu O(n^m)

Nu.. O(n*m) are doua for-uri doar. Primul ar fi un j de la 0 la m si al 2-lea ar fi un i de la 0 la n

m for-uri pentru vectori cu n elemente.

Presupunem un vector cu 3 elemente.

Daca il parcurgem cu un i de la 0 la 3 avem O(n)

Daca il parcurgem cu un for cu un j tot de la 0 la 3 care cuprinde si for-ul cu un i de la 0 la 3 avem 3*3=3^2 deci e O(n^2)

Daca le parcurgem pe cele dinainte cu inca un k avem 3*3*3=3^3 deci e O(n^3)

...

Daca avem m for-uri de tipul acesta avem O(n^m).

ce ai incercat si unde ai ajuns?

M-am uitat peste algoritmi cu complexitate 2^n, n^2(ca al lui em pentru cazul m=n), si superputeri(ackermann).

Nu am reusit sa gasesc un exemplu pt n^m.

Edited December 27, 2014 by crs12decoder

[MrGrj]

Uite aici o functie de complexitate O(n^m). Nu cred ca era asa greu:

waste(unsigned n, unsigned m) {
   if (m) 
      for(unsigned i=0; i<n; i++) 
         waste(n,m-1);
}

De asemenea, arunca un ochi aici

Edited December 27, 2014 by MrGrj

[em]

OK,

Dar eu nu cred ca e in regula nici exemplu tau pentru iterativ.

Adica, ar trebui sa fie un exemplu de algoritm clar, fara "..."

[crs12decoder]

Uite aici o functie de complexitate O(n^m). Nu cred ca era asa greu:

waste(unsigned n, unsigned m) {
   if (m) 
      for(unsigned i=0; i<n; i++) 
         waste(n,m-1);
}

De asemenea, arunca un ochi aici

Da, e bine, mersi

[MrGrj]

Da, e bine, mersi

Stiu ca e bine. Good luck