Это просто тестовая функция для вычисления сложности пространства, если мы рассмотрим количество кадров стека, чем это будет o (n), но как насчет этих массивов a и b внутри цикла и 2-d, которые также будут занимать некоторую память во всех рекурсивных звоните, мой профессор сказал нам, что сложность пространства - это размер фрейма стека, но он также потребляет некоторое пространство в этом цикле. Должен ли я рассматривать как фрейм стека, так и два массива и 2-мерный массив или дать какой-либо из них приоритет и почему ?
Я просто сосредотачиваюсь на космической сложности, поэтому забываю о результатах или сборке мусора
testfun(n){
if(n==0)
return;
int c[10][10];
int *a=malloc(sizeof(int)*n);
int *b=malloc(sizeof(int)*n);
for(int i=0;i<n;i++)
{ a[i]=n+2*i;
b[i]=n+3*i;
}
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
{
c[i][j]=1;
}
testfun(n-1);
free(a);
free(b);
}
Всего 3 ответа
Сложность пространства вопроса - O (n), если вы освободили ячейки памяти до вызова функции, так как каждый вызов функции должен помнить переменные стека.
free(a);
free(b);
test(n - 1);
Else в каждой функции вызывает функцию, выделяющую O (n) пространство и то же самое в последующих рекурсивных вызовах. Таким образом, сложность пространства O (n ^ 2).
Использование метода Substitution:
S(0) = 0
S(n) = S(n - 1) + 2n -------- (1)
S(n - 1) = S(n - 2) + 2 (n - 1) -------- (2)
S(n - 2) = S(n - 3) + 2 (n - 2) -------- (3)
Используя (1), (2), (3)
S(n) = S(n - 1) + 2n
S(n) = S(n - 2) + 2 (n - 1) + 2n
S(n) = S(n - 3) + 2(n - 2) + 2(n - 1) + 2n
.
.
.
.
S(n) = S(n - k) + 2(n - (k - 1)) + ... + 2n
Let k = n
S(n) = S(n - n) + 2(1) + 2(2) + ... 2(n)
S(n) = S(0) + 2(n * (n + 1)) / 2
S(n) = 0 + n^2 + n
Поэтому пространственная сложность O (n ^ 2).
Сложность пространства выше программы O(n^2). Причиной этого является то, что a and b имеют размер n, и, следовательно, обе они имеют пространственную сложность O(2n) которая не что иное, как O(n) . Теперь рекурсия просто от n to 1 и каждый вызов рекурсии потребляет пространство O(n) . Поэтому пространственная сложность будет O(n^2).
Возможно, вы думаете о free функции. Но рекурсия происходит до этой free функции. Следовательно, в каждом вызове функции зависит от значения входа ( i ), размер выделенного пространства равен 2i . Поскольку время остановки на n == 0 , общая пространственная сложность равна sum_{i = 1}^{n} 2*i = 2*n(n+1)/2 = Theta(n^2) .