Пространственно-временная сложность "вложенной" рекурсивной функции

Question

В одном из предыдущих вступительных экзаменов в cs возник вопрос: вычислите пространственную и временную сложность функции f1 как функции от n, предположите, что временная сложность malloc (n) равна O(1), а ее пространственная сложность равна На).

int f1(int n) {
    if(n < 3)
        return 1;

    int* arr = (int*) malloc(sizeof(int) * n);
    f1(f1(n – 3));
    free(arr);

    return n;
} 

Официальное решение: сложность времени: O(2^(n/3)), сложность пространства: O(n^2)

Я пытался решить ее, но я не знал, как, пока не увидел записку, в которой говорилось: так как функция возвращает n, мы можем рассматривать f (f (n-3)) как f (n-3) + f (n-3) или как 2f (n-3). В этом случае вопрос становится очень похожим на этот: Пространственная сложность рекурсивной функции

Я попытался решить это таким образом, и я получил правильный ответ.

Для сложности времени:

T (n) = 2T (n-3) +1, T (0) = 1

Т (п-3) = 2T (п-3 * 2) +1

Т (п) = 2 * 2T (п-3 * 2) + 2 + 1

Т (п-3 * 2) = 2T (п-3 * 3) + 1

Т (п) = 2 * 2 * 2T (п-3 * 3) + 2 * 2 + 2 + 1

...

Т (п) = (2 ^ к) Т (п-3 * к) + 2 ^ (к-1) +... 2 ^ 2 + 2 + 1

п-3 * к = 0

к = п / 3

===> 2 ^ (n / 3) +... + 2 ^ 2 + 2 + 1 = 2 ^ (n / 3) [1+ (1/2) + (1/2 ^ 2) +...] = 2 ^ (п / 3) * константа

Таким образом, я получил O (2 ^ (н / 3))

Для сложности пространства: глубина дерева n / 3, и каждый раз, когда мы делаем malloc, мы получаем (n / 3) ^ 2, таким образом, O (n ^ 2).

Мой вопрос:

• почему мы можем рассматривать f1 (f1 (n - 3)) как f1 (n-3) + f1 (n-3) или как 2f1 (n-3)?
• если функция не вернула n, а изменила ее, например: вернуть n / 3 вместо return n, то как мы ее решим? мы рассматриваем это как 2f1 ((n-3) / 3)?
• если мы не всегда можем рассматривать f1 (f1 (n-3)) как f1 (n-3) + f1 (n-3) или как 2f1 (n-3), то как мы рисуем дерево рекурсии и как мы написать и решить это с помощью индукционного метода T (n)?

Answer 1

• Почему мы можем рассматривать f1 (f1(n-3)) как f1(n-3) +f1(n-3) или как 2f1(n-3)?

  Потому что я) вложенный f1 вычисляется первым, а его возвращаемое значение используется для вызова внешнего f1; поэтому эти вложенные вызовы эквивалентны:

  int result = f1(n - 3);
  f1(result);
  

  ... и ii) возвращаемое значение f1 это просто его аргумент (за исключением базового случая, но это не имеет значения асимптотически), так что вышеизложенное эквивалентно следующему:

  f1(n - 3);
  f1(n - 3); // result = n - 3
  

• Если функция не вернула n, а изменила ее, например: вернуть n / 3 вместо return n, то как мы ее решим? мы рассматриваем это как 2f1 ((n-3) / 3)?

  Затрагивается только внешний вызов. Опять же, используя эквивалентное выражение из ранее:

  f1(n - 3); // = (n - 3) / 3
  f1((n - 3) / 3);
  

  т.е. просто f1(n - 3) + f1((n - 3) / 3) для вашего примера.

• Если мы не всегда можем рассматривать f1 (f1(n-3)) как f1(n-3) +f1(n-3) или как 2f1(n-3), то как нам нарисовать дерево рекурсии и как мы можем написать и решить это с помощью индукционного метода T (n)?

  Вы всегда можете разделить их на два отдельных вызова, как указано выше, и снова помните, что только на второй вызов влияет результат возврата. Если это отличается от n - 3 тогда вам понадобится дерево рекурсии вместо простого расширения. Разумеется, зависит от конкретной проблемы.