Решая рекуррентность T (n) = T (n/2) + 2T (n/4) + n?

Question

Я изучаю повторения, используя pdf-файл моего друга (Алгоритмы Unlocked) и пытается решить проблемы с рекуррентными моментами, и мне пока не ясно, что такое механика дерева рекурсии (я предполагаю, что это метод, который будет использоваться для этого проблема) и как сделать границы трудными, например, я хочу, чтобы константа была маленькой?

Answer 1

Постарайтесь развернуть свою рекуранцию, используя рекурсивное дерево. Вы будете иметь что-то вроде этого:

Recursive tree for T(n)

Смотрите, что каждый уровень имеет нерекурсивную сложность = п Расширяя Т (п), мы имеем 2 поддеревьев с разной высоты. Вы можете увидеть 2 высоты H1 и H2.

В настоящее время Т (п) ограничена сложностью 2 поддеревьев: п * Н1> = Т (п)> = п * Н2

Где: H1 = 1 + log_2 (п) и Н2 = 1 + log_4 (п)

Таким образом, решение будет O (nlog_2 (п))

Answer 2

Прежде всего, ознакомьтесь с предложением here и попытайтесь сделать что-то перед отправкой вопроса. Я отвечаю на это только потому, что мне было интересно освежить свои навыки.

---

Решение O(n log(n)).

Таким образом, вы должны увидеть, что теорема о главном не будет работать здесь, но Akra-Bazzi будет работать.

Так вот g(n) = n, a1 = 1, b1 = 1/2, a2 = 2, b2=1/4. Решая уравнение: a1*b1^p + a2*b2^p = 1 вы получаете p = 1.

Теперь решение интегрального вопроса int(1/u)du от 1 до x вы получите log(x). Таким образом, сложность O(x(1+log(x)), которая равна O(nlog(n)), где O - ограниченная граница.