Временная сложность рекурсивного алгоритма
Как я могу вычислить временную сложность рекурсивного алгоритма?
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;
}
}
5 ответов
Анализ рекурсивных функций (или даже их оценка) - нетривиальная задача. На мой взгляд, хорошее введение можно найти в книге Дона Кнута Конкретная математика .
Однако давайте сейчас проанализируем эти примеры:
Мы определяем функцию, которая дает нам время, необходимое функции. Предположим, что t (n) обозначает время, необходимое для pow (x, n) , то есть функция n .
Тогда мы можем заключить, что t (0) = c , потому что если мы вызовем pow (x, 0) , мы должны проверить, что ( n = = 0 ), а затем вернуть 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 на каждом шаге, требуется n-1 шагов, чтобы достичь t (n- (n-1)) = t (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) (см. раздел «Применение к популярным алгоритмам» в ссылке в Википедии, пример «Двоичный поиск»).
Это может быть немного сложно, но я думаю, что обычный способ - использовать теорему Мастера .
Сложность обеих функций, игнорирующих рекурсию, равна O (1)
Для первого алгоритма pow1 (x, n) сложность равна O (n), поскольку глубина рекурсии линейно коррелирует с n.
Для второй сложности O (log n). Здесь мы выполняем рекурсию примерно log2 (n) раз. Выкинув 2 получаем log n.
Давайте начнем с 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;
}
Теперь у вас есть итерационный алгоритм, и вы можете мне будет проще анализировать это таким образом.
Полагаю, вы возводите x в степень n. pow1 принимает O (n).
Вы никогда не меняете значение x, но каждый раз берете 1 из n, пока оно не дойдет до 1 (а затем вы просто вернетесь). Это означает, что вы выполните рекурсивный вызов n раз.