• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

złożoność pamięciowa

VPS Starter Arubacloud
0 głosów
2,643 wizyt
pytanie zadane 5 lutego 2017 w C i C++ przez partycja Nowicjusz (150 p.)
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?

1 odpowiedź

0 głosów
odpowiedź 5 lutego 2017 przez vector Dyskutant (9,200 p.)
edycja 5 lutego 2017 przez vector
 
Najlepsza

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.

komentarz 5 lutego 2017 przez partycja Nowicjusz (150 p.)
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....?)
komentarz 5 lutego 2017 przez vector Dyskutant (9,200 p.)

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

komentarz 5 lutego 2017 przez partycja Nowicjusz (150 p.)
edycja 5 lutego 2017 przez partycja
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ść).
komentarz 5 lutego 2017 przez vector Dyskutant (9,200 p.)

"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

Podobne pytania

0 głosów
3 odpowiedzi 311 wizyt
pytanie zadane 24 lutego 2023 w C i C++ przez polandonion Mądrala (7,270 p.)
0 głosów
1 odpowiedź 538 wizyt
pytanie zadane 4 czerwca 2018 w C# przez lukaszvip166 Początkujący (300 p.)

92,830 zapytań

141,771 odpowiedzi

320,817 komentarzy

62,159 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...