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

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

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

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


recurrence algorithm time-complexity master-theorem
person yahooo    schedule 01.10.2018    source источник
comment
объединить их в одно отношение. вы получите что-то вроде n ^ 3 + (n-1) ^ 2 в качестве стоимости текущего шага. Что ты видишь тогда?   -  person kelalaka    schedule 02.10.2018
comment
Подсказка: посмотрите на битовый шаблон n.   -  person meowgoesthedog    schedule 02.10.2018
comment
вы должны сказать = T(n) ={ 2T(**floor**(n/2)) + n^2, когда n четно, и T(n) = 2T(n/2) + n^3, когда n четно странно, или что-то еще.   -  person kelalaka    schedule 03.10.2018
comment
@kelalaka, наверное, ты имел в виду, что пол должен быть в нечетной части.   -  person Yola    schedule 03.10.2018
comment
@Йола. Ваше решение не завершено. потому что нечетное в конце сделает его кубическим?   -  person kelalaka    schedule 03.10.2018
comment
@kelalaka да, конечно, если n = 3 и T (3) является базовым случаем, то он может быть не кубическим. Я просто подумал, что это очевидно, и хотел, чтобы ответ был меньше. Но ты прав!   -  person Yola    schedule 03.10.2018
comment
@Yola Ответ действительно зависит от размера ввода с функцией пола.   -  person kelalaka    schedule 03.10.2018
comment
Я имел в виду, что вам нужно поставить пол в той части, когда n нечетно, а не четно.   -  person Yola    schedule 03.10.2018

Ответы (1)


arrow_upward
1
arrow_downward

Предположим, что 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 и оно равно базовому, тогда оно может быть не кубическим.

Поболтав с kelalaka, я понял, что если первый 1 это k справа в n, то если k > (2/3)(1/lg 2)lg n, то (n/2^k)^3 нас больше не волнует. Это все еще O(n^2).

person Yola    schedule 02.10.2018
comment
пусть говорят, что есть l четных k нечетных, где l+k = n. Когда будет n^2 и когда n^3. Отсюда это кажется довольно сложным. - person kelalaka; 03.10.2018
comment
@kelalaka Похоже, если l четное, а k нечетное, то n нечетное, поэтому у нас есть + n^3, что приводит нас к O(n^3). Неважно, что происходит на следующих уровнях. - person Yola; 03.10.2018
comment
3*2^n, все четные только один нечетный - person kelalaka; 03.10.2018
comment
Пусть m будет 8, поэтому n = 3*m^2 = 24. В двоичном формате это 11000. Вы можете разделить его три раза, и в конце концов вы получите n/8, это нечетно, поэтому вы применяете правило для нечетного, которое равно T(n/8) = T(n/16) + (n/8)^3 = T(..) + n^3/8^3, ну, это своего рода O(n^3). Но мы также можем видеть его как n^3/(n/3)^3 = 27, так что O(n^3) не является жесткой границей. Возможно, нам нужно учитывать позицию младшего значащего 1 в двоичном представлении n. - person Yola; 03.10.2018
comment
Это определенно, когда O(n^3) является жесткой границей. Мы получаем +n^3 на первом шаге. - person Yola; 03.10.2018
comment
поэтому, когда вы говорите, что это n ^ 2 или n ^ 3 - person kelalaka; 03.10.2018
comment
если первый 1 это k справа, то если k > (2/3)(1/lg 2)lg n, то (n/2^k)^3 нас больше не интересует. Это все еще O(n^2). - person Yola; 03.10.2018