Получите сложность T (n) = T (n/4) + T (3n/4) + c

Question

В этом рекуррентном соотношении T(n)=T(n/4)+T(3n/4)+c, у меня есть просто путаница в том, что каково отношение этого рекуррентного отношения к лучшему и в худшем случае, поскольку нам приходится решать обе подзадачи размером n/4 и 3n/4, так что же здесь терминология худшего случая или лучший анализ случаев здесь?

Кроме того, мы должны использовать здесь theta (log n) наш O (log n), хотя, видя приведенную ниже ссылку, я обнаружил, что O (log n) более применим, но все равно не получается, почему мы не используем theta (log n) Вот .

How to solve the recursive complexity T(n) = T(n/4)+T(3n/4)+cn

Answer 1

T(n) = T(n/4) + T(3n/4) + CONST <= 2T(3n/4) + CONST 

Мы будем использовать case 1 of master theorem с:

a = 2, b = 4/3. 
c = log_{4/3}(2) ~= 0.4 
CONST is in O(n^0.4) 

Таким образом, из основной теоремы, один хам получаем, что 2T(3n/4) + CONST в Theta(logn), и так как T(n) <= 2T(3n/4) + CONST, мы можем сказать, что T(n) является в O(logn).

Следуя ту же идею, но с нижней границей:

T(n) >= T(3n/4) + CONST ... 

И используя теорему мастер снова, мы можем сказать, что Т (п) также в Omega(logn).

Поскольку T (n) является как O (logn), так и Omega (logn), это также Theta (logn).

Что касается вашего вопроса, вы можете использовать либо обозначение Big-O, либо Theta, независимо от того, что вы предпочитаете. Как вы можете видеть, доказать, что Theta требует немного больше работы, но она также более информативна, так как она сообщает вам, что вы нашли туго.

Answer 2

Эти типы рецидивов можно легко решить с помощью теоремы Акра-Бацци (и если вы посмотрели на связанный с вами вопрос, кто-то показал вам решение аналогичной проблемы).

So 1/4^p + (3/4)^p = 1, где p = 1. В вашем случае g(u) = c, поэтому интеграл

Так int c/u^2 du из 1 to x, равной -1/u оцениваемой от 1 to x. Это равно -1/x + 1. Теперь, когда вы умножаете его на x, и вы поймете, что сложность O (n), а не O(log n), как предлагали другие люди.