Решите рекуррентное соотношение, используя метод Мастера -> T (n) = 2T (n / 2) + n ^ 2, когда n чётно, и T (n) = 2T (n / 2) + n ^ 3, когда n нечетно - PullRequest
Новая
       90

Решите рекуррентное соотношение, используя метод Мастера -> T (n) = 2T (n / 2) + n ^ 2, когда n чётно, и T (n) = 2T (n / 2) + n ^ 3, когда n нечетно

0 голосов
/ 01 октября 2018

T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

Я решил это отдельно, и я получаю решение как theta(n^2), если n четное, и theta(n^3), если n нечетное из случая 3 теоремы магистра.Но я не должен решать эту проблему отдельно.

Как решить такое рекуррентное отношение, как это вместе?

T(n) ={ 2T(n/2) + n^2 when n is even and T(n) = 2T(n/2) + n^3 when n is odd

Разрешаемо ли это по теореме магистра или теорема магистра не применима?

Пожалуйста, помогите мне с этим.

1 Ответ

0 голосов
/ 02 октября 2018

Предположим, n = 2^k для некоторого целого числа k, поэтому n равно 100...00.Затем вы можете применить мастер-метод к четной части повторения.и получите theta(n^2).

Теперь предположим, что 1 также не в старшем значащем бите, например, 100100..00.Таким образом, у вас будет хотя бы один уровень в вашем дереве рекурсии, все узлы которого составляют в сумме n^3 * constant, и тем самым вы получите theta(n^3).

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

После некоторого разговора с келалакой мне пришло в голову, что если сначала 1 будет k -й справа от n, тогда, если k > (2/3)(1/lg 2)lg n, нас больше не волнует (n/2^k)^3.Это все еще O(n^2).

...