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

Question

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

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;
    }
}

Answer 1

Анализ рекурсивных функций (или даже их оценка) - нетривиальная задача. Хорошее введение (на мой взгляд) можно найти в книге Дона Кнутса Конкретная математика .

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

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

.

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

Теперь рассмотрим другой случай: 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) (см. Раздел Применение к популярным алгоритмам в ссылке на википедию, пример «Бинарный поиск»).

Answer 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;
}

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

Answer 3

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

Answer 4

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

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

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

Answer 5

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

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