Временная сложность отношения разделяй и властвуй - PullRequest
Новая
       7

Временная сложность отношения разделяй и властвуй

0 голосов
/ 09 февраля 2019

Я пытался два вычислить временную сложность функции ниже.Я попробовал два разных метода

1) Так как почти каждый раз будет два рекурсивных вызова.мы можем записать рекуррентное отношение как T(n)=2T(n/2)+c.что дает нам O(logn).

2) Но мы можем также сказать, что общее количество рекурсивных вызовов будет равно n, что дает нам временную сложность как O(n).так как каждый раз номер получает половину, но есть два рекурсивных вызова.

какой из них правильный?

Здесь я увидел второй метод https://www.geeksforgeeks.org/write-a-c-program-to-calculate-powxn/

см. Временную сложность метода 1 в приведенной выше ссылке

Примечание-> Я знаю, что мы можем сохранить результат мощности (х, н / 2). 

/* Function to calculate x raised to the power n */

int power(int x, unsigned int n) 
{ 
    if (n == 0) 
        return 1; 
    else if (n%2 == 0) 
        return power(x, n/2)*power(x, n/2); 
    else
        return x*power(x, n/2)*power(x, n/2); 
}

Ответы [ 2 ]

0 голосов
/ 09 февраля 2019

Итак, T (n) = 2T (n / 2) + c. Фактически это само по себе O (n).

Вот формальное доказательство этому.T (n) = 2T (n / 2 ^ 1) + c (2 ^ 0)

Разбить его дальше

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

Упрощение этого:

T (n) = 2 ^ 2 T (n / 2 ^ 2) + c (2 ^ 0) + c(2 ^ 1)

Если разбить его дальше, что вы можете попробовать, вы получите выражение, подобное этому

T (n) = 2 ^ 3 T (n / 2 ^ 3) +c (2 ^ 0) + c (2 ^ 1) + c (2 ^ 2)

Теперь ключ в том, как далеко вы можете сломать его, это должно быть до такой степени, что 2 ^ что-то становится равнымn, так что n / n = 1 и T (1) является постоянным.

Это что-то легко может быть вычислено как log (n) base (2).

Таким образом, с помощью проверки вы можете предсказатьчто ваше окончательное выражение будет выглядеть так:

T (n) = 2 ^ log (n) T (n / 2 ^ log (n)) + c (2 ^ 0) + c (2 ^ 1) + ........ + 2 ^ (log (n) -1) 

=n T(1)+c(2^0+2^1+2^2+.......2^(log(n)-1))

=n T(1)+c(n-1)

Таким образом,

T (n) = (T (1) + c) nc, который является o (n).

0 голосов
/ 09 февраля 2019

1) Так как почти каждый раз будет два рекурсивных вызова.мы можем записать рекуррентное отношение как T(n)=2T(n/2)+c.что дает нам O(logn).

Вы как-то здесь ошиблись. T ( n ) = 2‍ T ( n / 2) + c не не дать O (log n );скорее это дает O ( n ).(Это относится к случаю 1 в https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms).)

2) Но мы можем также сказать, что общее количество рекурсивных вызовов будет равно n, что дает нам временную сложность как O(n).так как каждый раз номер становится наполовину, но есть два рекурсивных вызова.

Это правильно.

...