Jump to content
crs12decoder

O(n^m) recursiv

Recommended Posts

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)

Link to comment
Share on other sites

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 by em
Link to comment
Share on other sites

@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 by crs12decoder
Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



×
×
  • Create New...