Jak obliczyć złożoność przestrzeni funkcji?

Question

Zrozumiałem podstawową, że jeśli mam funkcję tak:

int sum(int x, int y, int z) { 
    int r = x + y + z; 
    return r; 
} 

wymaga 3 jednostki przestrzeni parametrów i 1 dla zmiennej lokalnej, a to nigdy się nie zmienia, więc jest to O(1).

Ale co, jeśli mam funkcji takiego:

void add(int a[], int b[], int c[], int n) { 
    for (int i = 0; i < n; ++i) { 
     c[i] = a[i] + b[0] 
    } 
} 

który wymaga jednostki N dla a, jednostek M dla b i L jednostek dla c i 1 jednostka dla i i n. Więc będzie potrzebować N+M+L+1+1 ilość pamięci.

Co będzie wielka szansa na złożoność przestrzeni? Ten, który zajmuje wyższą pamięć? tj. jeśli N ma wyższą macierzyństwo niż M i L (z dużo wyższych średnich przypuszczamy, że są większe niż 10**6) - czy można bezpiecznie powiedzieć, że złożoność przestrzeni to O(N), czy też nie tak, jak w przypadku złożoności czasowej?

Ale jeśli wszystkie trzy tj a, b, c nie są bardzo różni

Podobnie jak tej funkcji

void multiply(int a[], int b[], int c[][], int n) { 
    for (int i = 0; i < n; ++i) { 
     for (int j = 0; j < n; ++j) { 
      c[i] = a[i] + b[j]; 
     } 
    } 
} 

Więc co będzie złożoność przestrzeń? O(N+M+L)? A może największy?

Answer 1

Kiedy mówimy o złożoności przestrzeni, nie uważamy przestrzeni używanej przez dane wejściowe.

To pozwala nam mówić o algorytmach, które są stałą przestrzenią, O (log n) przestrzeni itp. Jeśli zaczęlibyśmy odliczać dane wejściowe, wtedy wszystkie algorytmy będą co najmniej liniową przestrzenią!

Standardowa definicja wielostrumieniowej maszyny Turinga również nie uwzględnia mocy wyjściowej.

Dane wejściowe są tylko do odczytu, a dane wyjściowe tylko do zapisu i nie wliczają się do złożoności powierzchni.

więc odpowiedzieć na pytanie: patrzeć na to, co metoda pamięć przydziela, w tym przestrzeni stosu dla zmiennych rekursji/lokalnych etc, i że będzie określić złożoność przestrzeni.

Answer 2

Złożoność przestrzenna algorytmu lub struktury danych to maksymalna ilość wykorzystanego miejsca w danym czasie, ignorując przestrzeń wykorzystywaną przez dane wejściowe do algorytmu. W związku z tym złożoność przestrzeni we wszystkich trzech przykładach w pytaniu to: O (1)