Сложность времени рекурсивного алгоритма

Как рассчитать сложность времени рекурсивного алгоритма?

int pow1(int x,int n) {
    if(n==0){
        return 1;
    }
    else{
        return x * pow1(x, n-1);
    }
}

int pow2(int x,int n) {
    if(n==0){
        return 1;
    }
    else if(n&1){
        int p = pow2(x, (n-1)/2)
        return x * p * p;
    }
    else {
        int p = pow2(x, n/2)
        return p * p;
    }
}

Ответы

Ответ 1

Анализ рекурсивных функций (или даже их оценка) является нетривиальной задачей. A (на мой взгляд) хорошее введение можно найти в Don Knuths Concrete Mathematics.

Однако проанализируйте эти примеры сейчас:

Определим функцию, которая дает нам время, необходимое для функции. Скажем, что t(n) обозначает время, необходимое для pow(x,n), т.е. Функцию n.

Тогда мы можем заключить, что t(0)=c, потому что, если мы вызываем pow(x,0), мы должны проверить, ((t25 > )), а затем вернуть 1, что можно сделать в постоянное время (следовательно, константа c).

Теперь рассмотрим другой случай: n>0. Здесь мы получаем t(n) = d + t(n-1). Это потому, что мы снова проверили n==1, вычислим pow(x, n-1, следовательно (t(n-1)) и умножим результат на x. Проверка и умножение могут выполняться в постоянное время (константа d), для рекурсивного вычисления pow требуется t(n-1).

Теперь мы можем "развернуть" термин t(n):

t(n) =
d + t(n-1) = 
d + (d + t(n-2)) = 
d + d + t(n-2) = 
d + d + d + t(n-3) =
... =
d + d + d + ... + t(1) =
d + d + d + ... + c

Итак, сколько времени потребуется, пока мы не достигнем t(1)? Поскольку мы начинаем с t(n) и мы вычитаем 1 на каждом шаге, для достижения t(n-(n-1)) = t(1) требуется n-1 шагов. Это, с другой стороны, означает, что мы получаем n-1 раз константу d, а t(1) оценивается как c.

Итак, получаем:

t(n) =
...
d + d + d + ... + c =
(n-1) * d + c

Итак, мы получаем, что t(n)=(n-1) * d + c, являющийся элементом O (n).

pow2 можно выполнить с помощью теоремы Мастера. Поскольку мы можем предположить, что функции времени для алгоритмов монотонно возрастают. Итак, теперь у нас есть время t(n), необходимое для вычисления pow2(x,n):

t(0) = c (since constant time needed for computation of pow(x,0))

для n>0 получаем

        / t((n-1)/2) + d if n is odd  (d is constant cost)
t(n) = <
        \ t(n/2) + d     if n is even (d is constant cost)

Вышеуказанное может быть "упрощено":

t(n) = floor(t(n/2)) + d <= t(n/2) + d (since t is monotonically increasing)

Итак, мы получаем t(n) <= t(n/2) + d, который может быть решен с использованием магистерской теоремы для t(n) = O(log n) (см. раздел "Применение к популярным алгоритмам" в ссылке wikipedia, пример "Бинарный поиск" ).

Ответ 2

Давайте просто начнем с pow1, потому что это самый простой.

У вас есть функция, когда в O (1) выполняется один прогон. (Проверка условий, возврат и умножение являются постоянным временем.)

То, что у вас осталось, - это ваша рекурсия. Что вам нужно сделать, так это проанализировать, как часто функция в конечном итоге вызывает себя. В pow1 это произойдет N раз. N * O (1) = O (N).

Для pow2 это тот же принцип - один запуск функции выполняется в O (1). Тем не менее, на этот раз вы вдвое сокращаете N каждый раз. Это означает, что он будет запускать log2 (N) раз - эффективно один раз за бит. log2 (N) * O (1) = O (журнал (N)).

Что-то, что может вам помочь, заключается в том, чтобы использовать тот факт, что рекурсия всегда может быть выражена как итерация (не всегда очень просто, но это возможно). Мы можем выразить pow1 как

result = 1;
while(n != 0)
{
  result = result*n;
  n = n - 1;
}

Теперь у вас есть итеративный алгоритм, и вам может быть проще проанализировать его таким образом.

Ответ 3

Это может быть немного сложным, но я думаю, что обычный способ - использовать Мастер-теорему.

Ответ 4

Сложность обеих функций, игнорирующих рекурсию, равна O (1)

Для первого алгоритма pow1 (x, n) сложность O (n), поскольку глубина рекурсии коррелирует с n линейно.

Для второй сложности O (log n). Здесь мы возвращаем приблизительно log2 (n) раз. Выбрасывая 2, мы получаем log n.

Ответ 5

Итак, я предполагаю, что вы поднимаете x до власти n. pow1 принимает O (n).

Вы никогда не изменяете значение x, но каждый раз вы принимаете 1 из n, пока не достигнете 1 (и вы просто вернетесь). Это означает, что вы будете делать рекурсивный вызов n раз.