Расчет сложности времени рекурсивного алгоритма - PullRequest
Новая
       5

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

2 голосов
/ 01 февраля 2011

Я пытаюсь вычислить временную сложность рекурсивного алгоритма, и я думаю, что я почти получил его. Вот псевдокод, на который я смотрел: 

long pow( long x, int n ) {
    if (n == 0)
        return 1;
    if (n == 1)
    return x;
    if(isEven(n))
        return pow(x, n / 2 ) * pow(x, n / 2);
    else
        return x * pow(x * x, n / 2);
}

isEven просто определяет, является ли целое число, переданное ему, четным или нет, и для данного примера работает в постоянном времени.

Итак, если n = 0 или n = 1, он работает, он работает с постоянным временем, например: f (n) = C0. Однако, когда n> 1, он должен работать так: f (n) = f (n-1) + f (n-1) + C1, если n чётно, и f (n) = f (n-1) + 1, когда n нечетно, верно? Или это должно быть: f (n) = f (n / 2) + f (n / 2) + C1, если n четное, и f (n) = f (n / 2) + 1, если n нечетное?

Я смотрел на множество примеров. Здесь я нашел очень полезным. Моя проблема связана с двумя рекурсивными вызовами, когда n чётно - я не совсем уверен, что здесь делать. Если бы кто-нибудь мог указать мне правильное направление, я был бы очень благодарен.

Ответы [ 2 ]

3 голосов
/ 01 февраля 2011

Взгляните на Основную теорему .Вы можете рассматривать это как алгоритм «разделяй и властвуй».

Конечный результат заключается в том, что при наличии двух рекурсивных вызовов вы получите наихудший вариант выполнения O (n).Например, pow (x, 4) вызывает pow (x, 2) дважды, а pow (x, 1) четыре раза;в общем случае степень два приведет к n * 2-1 вызовам.

Также обратите внимание, что, просто вызвав pow (x, n / 2) один раз и возведя в квадрат результат в этой ветви, алгоритм становится Oжурнал n).

0 голосов
/ 01 февраля 2011

Давайте определим f (m) как число операций задачи с размером m.«Проблема» - это, конечно, возведение в степень (пау), как x^n или pow(x,n).Функция long pow( long x, int n ) { не должна выполнять больше или меньше работы, если я изменяю x.Таким образом, размер возведения в степень не зависит от x.Это, однако, зависит от п.Скажем, 2 ^ 4 имеет размер 4, а 3 ^ 120 имеет размер 120. (Имеет смысл, если вы видите, что 2^4=2*2*2*2 и 3^120=3*3*3*3*..*3) Таким образом, размер проблемы равен n, второму параметру.Мы могли бы, если хотите, сказать, что размер проблемы равен 2 * log (n), но это было бы глупо.

Теперь у нас есть f (m) - число операций для вычисления pow(x,m) для любогоИкс.Потому что pow(x,m) это как раз проблема с размером m. Итак, если у нас есть pow(x,y), то количество операций по определению равно f(y). Например, pow(3,3*m/2) имеет f(3*m/2) операций.

Наконец, давайте посчитаемоперации 

long pow( long x, int n ) {
    if (n == 0)  //1
        return 1;
    if (n == 1)  //1
    return x;
    if(isEven(n)) //1
        return pow(x, n / 2 ) * //that is f(n/2), y=n / 2
                 pow(x, n / 2); //also f(n/2)
    else
        return x * pow(x * x, n / 2); //1+1+f(n/2)
}

Принимая это вместе: f(n) = 2*f(n/2) + c1 (n четное) и f(n) = f(n/2) + c2 (n четное).Если вас интересует только наихудший сценарий, обратите внимание, что в нечетном случае меньше работы.Таким образом, f (n) ограничено сверху четным случаем: f(n) <= 2*f(n/2)+c.

...