złożoność pamięciowa

Question

Witam :)

Jak liczy się złożoność pamięciową funkcji rekurencyjnej?

Chodzi tu dokładnie o sortowanie przez scalanie, wywoływane z parametrami (int l, int p, int A[max]), ponadto w każdym wykonaniu funkcji tworzona jest tablica pomocnicza B[max], w treści funkcji rekurencyjnie wywoływana jest ona dwa razy plus pojawiają się pętle.

Moja sugestia S(n)=2S(n/2)+o(n), ale nie jestem co do niej przekonana. Jakieś wskazówki?

Licząc złożoność pamięciową, bierze się również pod uwagę parametry, z którymi funkcja została wywołana, prawda?

Answer 1

1) Złożoność pamięciową liczy się bardzo podobnie co złożoność obliczeniową z różnicą że liczysz wykorzystanie pamięci a nie mocy obliczeniowej. Ma to zastosowanie również w rekurencji.

2) Złożoność pamięciowa sortowania przez scalanie zależy od konkretnej implementacji, aczkolwiek zakładam że chodzi Ci o najbardziej intuicyjną implementację, mniej więcej wyglądającą jak ta:
 

void merge(int *array, int i, int j, int k, int l) {
    int *tempArray = new int[l-i];

    // ...

    delete [] tempArray;
}

void mergeSort(int *array, int i, int j) {
    if(j - i <= 1) {
        return;
    }

    int mid = (i + j) / 2;
    mergeSort(array, i, mid);     // Tutaj używamy S(n/2) pamięci
    mergeSort(array, mid, j);     // Tutaj używamy S(n/2) pamięci
    merge(array, i, mid, mid, j); // Tutaj używamy O(n)   pamięci gdzie n = j-i
}

Można zauważyć iż dodatkową pamięć wykorzystujemy dopiero po wykonaniu sortowania częściowego więc złożoność pamięciową w tym przypadku można wyrazić przez ciąg:

S(n) = max{S(n/2), S(n/2), O(n)} + O(1)
S(1) = O(1)

Bierzemy maksimum a nie sumę tych wartości ponieważ po zakończeniu funkcji wywoływanych w środku sortowania cała używana przez nich pamięć jest uwalniana. Rozwiązując ciąg rekurencyjny otrzymujemy O(n)

3) Raczej bierze się pod uwagę ograniczenia dolne/górne niżeli same parametry z którymi funkcja została wywołana przy liczeniu złożoności. Tyczy się to zarówno złożoności obliczeniowej jak i pamięciowej.

Comments

Nasze scalanie jest dużo bardziej prymitywne, bo nie skupialiśmy się na jak najkrótszym kodzie:

void scalanie(int l, int p,int A[100]){
    int i, j, k, m, B[100];
    k=(l+p)/2;
    if(l < k)               
        scalanie(l,k,A);   
    if(k+1 < p)             
        scalanie(k+1,p,A);  
    i=l;  j=k+1; m=0;
    while(i<=k && j<=p){
        if(A[i]<A[j])
            B[m++]=A[i++];
        else
            B[m++]=A[j++];
    }
    while(i<=k){
        B[m++]=A[i++];
    }
    while(j<=p){
        B[m++]=A[j++];
    }
    for(i=0; i<=p-l; i++)
        A[l+i]=B[i];
}

Zawsze tworzymy tablicę o tym samy rozmiarze.
Tutaj rozumowanie przebiega analogicznie?

I skąd się bierze tam maksimum? (liczę największe możliwe wykorzystanie pamięci czy ma to jakiś związek z regułą sumowania....?)

---

1) Nie jest do końca analogicznie ponieważ tworzysz tymczasową tablicę już na samym początku, mianowicie wzór będzie teraz

S(n) = O(x) + max{S(n/2), S(n/2}}

S(1) = O(x)

gdzie x = 100 aczkolwiek x >= n przez co ten algorytm jest bardzo niewydajny pamięciowo

2) Bierzesz maksimum ponieważ chcesz policzyć maksymalne zużycie pamięci

---

Mamy też drugą część polecenia, by wyznaczyć złożoność pamięciową tego algorytmu (tzn. "minimalną liczbę komórek pamięci potrzebnych do przechowywania sortowanych liczb i potrzebnych do prawidłowego działania algorytmu"), ale przy przyjęciu, że rozmiar deklarowanych tablic to ROZMIAR=n=2^k dla pewnego naturalnego k. (to założenie o n=2^k jest przyjęte, by mieć pewność, że za każdym razem funkcja uruchomi się rekurencyjnie dwa razy i nie zostanie jeden element, prawda?)

Czyli teraz S(n)=o(n)+max{S(n/2),S(n/2)}, czyli właściwie S(n)=o(n)+S(n/2) i dalej działam z twr. o rekursji uniwersalnej? (zakładam, że egzaminator liczy na jakąś konkretną asymptotyczną złożoność).

---

"minimalną liczbę komórek pamięci potrzebnych do przechowywania sortowanych liczb i potrzebnych do prawidłowego działania algorytmu" brzmi to dla mnie jakby oczekiwał dokładną liczbę bajtów uzależnionych od k.

Założenie o n=2^k jest po to aby nigdzie w rachunkach nie trzeba było używać podłogi/sufitu przy dzieleniu przez 2.

S(n)=O(n)+S(n/2) jeżeli już, ale to nie pomoże przy wyliczeniu dokładnej ilości pamięci