Я пытаюсь использовать деревья рекурсии, чтобы найти асимптотическую сложность этой функции:
T(n) = T(n/3) + T(n/2) + n, если n > 5; иначе T(n) = 1
Я сделал дерево рекурсии и определил, что каждый уровень имеет сложность _(5/6)^k * n_ на каждом уровне. Отсюда я не уверен, как действовать. Я знаю, что мне нужно выяснить сложность глубины, но не совсем уверен, как это сделать.
В качестве подсказки используйте формулу суммы геометрического ряда:
1 + (5/6) + (5/6)2 + (5/6)3 + ... = 1 / (1 - 5/6) = 6
Надеюсь это поможет!
Этот тип рекурсии можно легко решить с помощью метода Akra-Bazzi. В вашем случае a1=a2=1, b1 = 1/3, b2=1/2 и g(n) = n.
Решение 1/3^p + 1/2^p = 1 вашего p=0.7878. Теперь вам нужно решить интеграл, и все готово.
Здесь доминирует x, поэтому ваша сложность O(n)
