что такое пространственная сложность для этой программы?

Это просто тестовая функция для вычисления сложности пространства, если мы рассмотрим количество кадров стека, чем это будет 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); 
  }

c algorithm

Всего 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) .