kavinderrana121 Ответов: 2

Является ли пространственная сложность приведенной ниже программы правильной?

Я должен вычислить сложность пространства для этой функции, если мы видим в соответствии с размером стека, то это будет O(n), но в каждом рекурсивном вызове два массива потребляют дополнительное пространство, которое составляет 2n или порядка O(n)

СВОИ СОМНЕНИЯ

1)Когда мы вычисляем временную сложность для этой функции, процесс будет выглядеть следующим образом: при каждом рекурсивном вызове O(n) дополнительное пространство занимает два массива(я беру только порядок 2n ), а поскольку размер стека равен O(n), то пространственная сложность равна O(n^2)

2) что произойдет, если я заменю эти два массива 2d-массивом, то при каждом рекурсивном вызове O(n^2) будет занято дополнительное пространство, а поскольку размер стека равен O(n), то сложность пространства на этот раз будет O(n^3)

Примечание ничего особенного в этой функции нет только вычисление сложности пространства оставьте значение мусора так как я не освобождаю память после рекурсии

Что я уже пробовал:

testfun(n){
  if(n==0)
  return;

  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;
  }

  testfun(n-1);
  free(a);
  free(b);

  }

Обратите внимание, я освобождаю память через рекурсию

kavinderrana121

@OriginalGriff, пожалуйста, помогите, сэр

2 Ответов

Рейтинг:
2

Patrice T

Цитата:
СВОИ СОМНЕНИЯ

Не сомневайся, убедись.
Определите глобальную переменную, счетчик,
чанье ваш код таким образом
testfun(n){
  if(n==0)
  return;

  int *a=malloc(sizeof(int)*n);
  counter += n;
  int *b=malloc(sizeof(int)*n);
  counter += n;
  for(int i=0;i<n;i++)
  {  a[i]=n+2*i;
     b[i]=n+3*i;
  }

  testfun(n-1);
  free(a);
  free(b);

  }

затем измените вызов функции на
counter = 0;
testfun(n);
// at this point, counter contain the total memory allocated to arrays over recursion

Рейтинг:
1

CPallini

С такой функцией, когда N кроме того, вы можете смело игнорировать пространство, занимаемое распределением стека.
В куче, из-за рекурсивных вызовов, которые у вас есть

memory(N) = 2*N + .. + 4 + 2
то есть
memory(N) = 2*N!
(измеряется в sizeof(int), конечно).
Таким образом, сложность функционального пространства равна
O(N!)

Извините, что я допустил грубую ошибку (большое спасибо Патрис Ти за то, что заметил его). Я фактически умножил то, что должен был добавить вместо этого.
Так
memory(N) = N(N+1)

А сложность функционального пространства такова 
O(N^2)

Patrice T

Вы уверены насчет"!"?

CPallini

ОЙ. Вы правы, я допустил грубую ошибку (умножение вместо сложения) Я собираюсь внести в него поправки.
Большое вам спасибо, что указали на это.
(Теперь я надеюсь, что это правильно).