Решите рекуррентное уравнение T (n) = T (n / 3) + O (1), используя итерацию или замену

Question

Я понимаю, что решение этого с помощью теоремы Учителя дает ответ Большой Тэты (log n). Тем не менее, я хочу знать больше и найти основание логарифма. Я попытался прочитать о теореме мастеров больше, чтобы узнать о базе, но не смог найти больше информации о википедии (https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)).

Как бы я решил эту проблему, используя дерево рекурсии или метод замещения для решения рекурсий? можно предположить, что n = 2 ^ K и T (0) = 0.

Answer 1

Не устанавливать n=2^k, но n=3^k

, таким образом T(3^k) = T(3^{k-1}) + c

повторение становится w_k = w_{k-1} + c

Принимая T(1) = 1 с общим термином:w_k = ck+1 и w_0 = 1

вы заключаете T(n) = clog_3(n) + 1

и, таким образом, T(n) = O(log_3(n))

Answer 2

T(n) = T(n/3) + O(1) = T(n/9) + O(1) + O(1) = T(n/27) + O(1) + O(1) + O(1) = …

После log3(n) шагов термин T исчезает и T(n) = O(log(n)).