рекурсия Дерев и асимптотическая Сложность: Т (п) = Т (п/3) + Т (п/2) + п

Question

Я пытаюсь использовать рекуррентные дерева, чтобы найти асимптотическую сложность этой функции:

T (n) = T (n/3) + T (n/2) + n если n> 5; в противном случае Т (п) = 1

Я сделал дерево рекурсии и определили, что каждый уровень имеет _ (5/6)^K * N_ сложности на каждом уровне. Отсюда я не уверен, как действовать дальше. Я знаю, что мне нужно выяснить сложность глубины, но на самом деле не знаю, как это сделать.

Answer 1

В качестве подсказки, использовать формулу для суммы геометрической прогрессии:

1 + (5/6) + (5/6) + (5/6) + ... = 1/(1 - 5/6) = 6

Надеюсь, что это поможет!

Answer 2

Этот тип рекурсии можно легко решить, используя Akra-Bazzi method. В вашем случае a1=a2=1, b1 = 1/3, b2=1/2 и g(n) = n.

Решение 1/3^p + 1/2^p = 1p=0.7878. Теперь вам нужно решить интеграл, и все готово.

Это доминирует x и поэтому ваша сложность O(n)