Использование метода Akra-Bazzi, безусловно, является отличным решением.
Приведенное ниже решение о дереве повторений неверно. Найдите причину в комментариях.
Просто оставьте здесь решение неправильное на случай, если кому-то интересно или совершит ту же ошибку.
Вот решение из дерева повторений.
Для уровня h он будет выглядеть следующим образом:
T (N) = 3 ^ h * T (N / 3 ^ h) + T (N / 2 ^ h) + \ sum\ limit_ {i = 1} ^ {h-1} (3 ^ {i-1} + 3 ^ i) * T (N / (3 ^ i 2 ^ {hi}))
, что означаетуровень h дает
N
Аобратите внимание, что высота дерева повторений составляет от
(\ log_2 N, \ log_3 N)
Таким образом, нотация big-Oh равна
O (N logN)
(просто хочу проиллюстрировать, что рекуррентное дерево является возможным решением.