Afişează mesaje
Sigur enuntul este bun?
Am dubii ca acea complexitate nu depinde si de m. De exemplu sa luam cazul particular m=n^3 si numerele sa fie:
n^3+1 n^3+2 ... n^3+n | 1 2 ... n^3. In acest sir niciun numar nu se afla in pozitia lui finala, deci ar trebui ca din O(n^2) operatii sa rearanjam O(n^3) numere cu consum constant de memorie. Asta nu se poate!!! Inclin sa cred ca acea complexitate ar trebui sa fie O(n*m) sau asa ceva.
|
|||||||||||||||||||
