Определение сложности для рекурсивных функций (запись Big O)

Завтра у меня есть компьютерная наука, и мне нужна помощь в определении сложности этих рекурсивных функций. Я знаю, как решать простые случаи, но я все еще пытаюсь научиться решать эти более сложные случаи. Это были лишь некоторые из примеров проблем, которые я не мог понять. Любая помощь была бы высоко оценена и очень помогла бы в моих исследованиях, спасибо!

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{
    for (i = 0; i < n; i += 2) {
        // do something
    }

    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun5(n-5);
}

Ответы

Ответ 1

Временная сложность в нотации Big O для каждой функции в численном порядке:

  • Первая функция вызывается рекурсивно n раз до достижения базового аргумента, поэтому ее O(n), которую часто называют linear.
  • Вторая функция называется n-5 для каждого времени, поэтому мы вычитаем пять из n перед вызовом функции, но n-5 также O(n). (На самом деле называется порядком n/5 раз, и O (n/5) = O (n)).
  • Эта функция представляет собой log (n) base 5, для каждого раз мы делим на 5 перед тем как вызывать функцию так, чтобы ее O(log(n)) (база 5), часто называемая логарифмической, и чаще всего анализ нотации и сложности Big O использует базу 2.
  • В четвертом, это O(2^n) или экспоненциальный, поскольку каждая функция вызывает вызов дважды, если она не была рекурсивно n.

  • Что касается последней функции, цикл for принимает n/2, так как мы возрастаем на 2, а рекурсия принимает n-5 и поскольку цикл for вызывается рекурсивно, поэтому сложность времени находится в (n-5) * (n/2) = (2n-10) * n = 2n ^ 2- 10n, из-за асимптотического поведения и наихудшего сценария или верхней границы, что большой O стремясь, нас интересует только наибольший член, поэтому O(n^2).

    Удачи вам на ваших промежуточных уровнях;)

Ответ 2

В случае, когда n <= 0, T(n) = O(1). Следовательно, временная сложность будет зависеть от того, когда n >= 0.

Мы рассмотрим случай n >= 0 в части ниже.

1.

T(n) = a + T(n - 1)

где a - некоторая константа.

По индукции:

T(n) = n * a + T(0) = n * a + b = O(n)

где a, b - некоторая константа.

2.

T(n) = a + T(n - 5)

где a - некоторая константа

По индукции:

T(n) = ceil(n / 5) * a + T(k) = ceil(n / 5) * a + b = O(n)

где a, b - некоторая константа, k <= 0

3.

T(n) = a + T(n / 5)

где a - некоторая константа

По индукции:

T(n) = a * log5(n) + T(0) = a * log5(n) + b = O(log n)

где a, b - некоторая константа

4.

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

где a - некоторая константа

По индукции:

T(n) = a + 2a + 4a + ... + 2^n * a + T(0) * 2 ^ n 
     = a * 2^(n+1) - a + b * 2 ^ n
     = (2 * a + b) * 2 ^ n - a
     = O(2 ^ n)

где a, b - некоторая константа.

5.

T(n) = n / 2 + T(n - 5)

Мы можем по индукции доказать, что T(5k) >= T(5k - d) где d = 0, 1, 2, 3, 4

Write n = 5m - b (m, b - целое число, b = 0, 1, 2, 3, 4), то m = (n + b) / 5:

T(n) = T(5m - b) <= T(5m)

(На самом деле, чтобы быть более строгим здесь, следует определить новую функцию T'(n) такую, что T'(5r - q) = T(5r) где q = 0, 1, 2, 3, 4. Мы знаем T(n) <= T'(n) как доказано выше. Когда мы знаем, что T'(n) находится в O(f), что означает, что существуют константа a, b, так что T'(n) <= a * f(n) + b, мы можем получить, что T(n) <= a * f(n) + b и, следовательно, T(n) находится в O(f). Этот шаг на самом деле не нужен, но легче думать, когда вы не нужно иметь дело с остатком.)

Расширение T(5m):

T(5m) = 5m / 2 + T(5m - 5) 
      = (5m / 2 + 5 / 2) * m / 2 + T(0) 
      = O(m ^ 2) = O(n ^ 2)

Следовательно, T(n) есть O(n ^ 2).

Ответ 3

Один из лучших способов найти для аппроксимирования сложности рекурсивного алгоритма - это рисование дерева рекурсии. Когда у вас есть рекурсивное дерево:

Complexity = length of tree from root node to leaf node * number of leaf nodes
  • Первая функция будет иметь длину n и количество листов node 1, поэтому сложность будет n*1 = n

  • Вторая функция будет иметь длину n/5 и количество листовых узлов снова 1, поэтому сложность будет n/5 * 1 = n/5. Он должен быть приближен к n

  • Для третьей функции, поскольку n делится на 5 на каждый рекурсивный вызов, длина рекурсивного дерева будет log(n)(base 5), а число листовых узлов снова 1, поэтому сложность будет log(n)(base 5) * 1 = log(n)(base 5)

  • Для четвертой функции, так как каждый node будет иметь два дочерних узла, количество листовых узлов будет равно (2^n), а длина рекурсивного дерева будет log n, поэтому сложность будет (2^n) * log n. Но так как log n не имеет значения перед log n, его можно игнорировать, а сложность можно назвать только (2^n).

  • Для пятой функции есть два элемента, вводящих сложность. Сложность, введенная рекурсивным характером функции и сложности, введенная циклом for в каждой функции. Выполняя приведенный выше расчет, сложность, возникающая при рекурсивном характере функции, будет ~ n и сложностью, обусловленной циклом n. Общая сложность будет n*n.

Примечание. Это быстрый и грязный способ вычисления сложности (ничего официального!). Хотелось бы услышать отзывы об этом. Спасибо.