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

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

0 голосов
/ 26 сентября 2018

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

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

T (n-3) = 2T (n-3 * 2) + 1

T (n) = 2 * 2T (n-3 * 2) + 2 + 1

T (n-3* 2) = 2T (n-3 * 3) + 1

T (n) = 2 * 2 * 2T (n-3 * 3) + 2 * 2 + 2 + 1

...

T (n) = (2 ^ k) T (n-3 * k) + 2 ^ (k-1) + ... + 2 ^ 2 + 2 +1

n-3 * k = 0

k = n / 3

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

Таким образом, я получил O (2 ^ (n / 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 вместо n, как мы ее решим?мы рассматриваем это как 2f1 ((n-3) / 3)?
  • , если мы не можем всегда рассматривать f1 (f1 (n - 3)) как f1 (n-3) + f1 (n-3) или как 2f1 (n-3), тогда как мы рисуем дерево рекурсии и как мы пишем и решаем его, используя индукционный метод T (n)?

1 Ответ

0 голосов
/ 26 сентября 2018

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

    Поскольку i) вложенный 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, вам понадобится дерево рекурсии вместо простого расширения.Разумеется, зависит от конкретной проблемы.

...