Problema saptamanii - Interclasare

[•Cosmin]

Ziceam ca e voie sa folosim memorie suplimentara O(1). Daca ai o lista inlantuita iti trebuie ceva memorie pentru pointerii listei nu?

[•bdragu]

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.

[•marius135]

@ Dragu Ionut-Bogdan O(N^2) se referea la O( (N + M)^2).

[•Cosmin1490]

Inserarea unui element intr-un vector merge in timp liniar.
Si daca vrem sa inseram elementele ce fac parte din M in N atunci vine N*M nu?
Cum stim ca vectorii sunt deja sortati la o singura parcurgere a lui N si M inserari e gata.
Si in cazu asta vine N+N*M care e mai putin decat (N+M)^2 si cu Memorie O(1).
Se incadreaza? sau gresesc la rationament?
[LE]: ca sa fie mai clar: cand zic inserare...  ma refer la asezarea lui pe pozitia finala, pt ca practic elementele sunt deja in vector si trebuie doar sa "dam mai incolo" cu o pozitie elementele, sa aiba loc cel care trebuie asezat, "dand mai incolo" suprascriem pozitia originala iar in golul lasat copiem dintr-un aux .

[•blasterz]

tot O(n^2) e ... deci nu se incadreaza... trebuie sa gasesti un algoritm care sa aiba o clasa inferioara lui O(n^2)
(exemple: O(nlogn), O(n sqrt n) , O(n log^2n)...)

[•crushack]

Am o idee , daca pe masura ce dau de numere <= N le mut la inceputul vectorului ?
Un fel de:

Cod:

p=0;
for (i=0;i<N+M;i++)
   if (v[i]<=N)
   { 
       schimb(v[p],v[i]);
       p++;
    }

Prin schimb se intelege interschimbare.
Cam ce complexitate e ?

Modificat de Moderator: Foloseste tag-ul [ code ] ... [ / code ] atunci cand postezi cod sursa

[•skyel]

Cred ca metoda propusa de tine nu numai ca nu sorteaza, dar nu modifica vectorul, in contextul in care prin v te referi la v(i), iar toate numerele sunt <= N. Daca sunt distribuite random(respectand cerinta), il face praf...

L.E.: Pe viitor ai putea sa folosesti tagul de code ca sa nu iti mai considere [ i ] ca fiind tag-ul de inceput pentru italic text.

[•Robybrasov]

Se considera memorie neconstanta la un algoritm recursiv? Ma refer aici la stiva in care urca si coboara recurenta, care depinde totusi de N.