Теоретически логарифмическая сложность, но практически ее линейная - PullRequest
Новая
       49

Теоретически логарифмическая сложность, но практически ее линейная

0 голосов
/ 08 февраля 2012

Посмотрите на следующий код, чтобы найти X ^ y. 

/* Find exponent in logarithmic complexity */
int findPower(int base, exponent){
     if( 1 == exponent ) return base;
     return (findPower(base, exponent/2)*findPower(base, exponent-exponent/2));
}

int main(int argc, char *argv[]){
    if(argc < 3) {
        printf("Usage :: logpow baseNumber power\n");
        return -1;
    }
    printf("%s ^ %s  =  %d\n", argv[1], argv[2], findPow( atoi(argv[1]),
                                                          atoi(argv[2])) );
    return 0;
}

Анализ показывает, что это имеет сложность тета (log (n)).Но я запустил его, чтобы измерить время, и вот результаты 

Run 1: (calculating 1^500_million)
user-lm Programming # time ./a.out 1 500000000
1 ^ 500000000  =  1

real    0m5.009s
user    0m5.000s
sys 0m0.000s


Run 2: (calculating 1^1_Billion)
user-lm Programming # time ./a.out 1 1000000000
1 ^ 1000000000  =  1

real    0m9.667s
user    0m9.640s
sys 0m0.000s


Run 3: (calculating 1^2_Billion)
user-lm Programming # time ./a.out 1 2000000000
1 ^ 2000000000  =  1

real    0m18.649s
user    0m18.630s
sys 0m0.000s

Сверху видно, что сложность реального времени имеет линейное, а не логарифмическое значение!

В чем может быть причиназа такую ​​огромную разницу в сложности?

С уважением,

Микроядро

Ответы [ 3 ]

11 голосов
/ 08 февраля 2012

Вы фактически вызываете 2 вызова функции из каждого вызова. Дерево рекурсии было бы двоичным деревом высотой log(exponent), поэтому число узлов в нем будет 2^log(exponent) == exponent. Таким образом, в целом это становится линейным алгоритмом. Вы можете переписать его так, чтобы повысить производительность: 

int findPower(int base, int exponent){
    if( 0 == exponent ) return 1;
    int temp = findPower(base, exponent/2);
    if(exponent % 2 == 0) return temp * temp;
    return temp * temp * base;
}

Хитрость в том, что вы должны сохранить значение findPower(base, exponent/2), чтобы получить логарифмическую сложность. Дерево рекурсии по-прежнему имеет высоту log(exponent), но у каждого узла теперь только один дочерний элемент, поэтому будет log(exponent) узлов. Если вы на самом деле вызовете его дважды, это ухудшит производительность даже более, чем линейную. Нет необходимости вычислять одно и то же значение во второй раз, если оно у вас уже есть!

Как заметил @David Schwartz, количество вызовов, сделанных в вашем коде, удвоится, если exponent удвоится. Но когда вы сохраняете значения, удвоение exponent делает только один больше вызовов.

4 голосов
/ 08 февраля 2012

Ваш анализ неверен, это O (N).

Когда вы поднимаете N с 1 миллиарда до 2 миллиардов, вам нужно выполнить две силовые операции на 1 миллиард.Таким образом, удвоение N удваивает работу, которую необходимо выполнить.Это O (N).

2 голосов
/ 08 февраля 2012

Существует формальное представление сложности вашего алгоритма:

T(n) = 2T(n/2) + c

Где n - показатель степени.Что дает

T(n) = Theta(n)

Анализ неверен.

...