Решение рекуррентности T (n) = T (n / 2) - T (n / 6) + O (lg n) с использованием метода основной теоремы?

Question

. Решение рекуррентности T (n) = T (n / 2) - T (n / 6) + O (lg n) с использованием метода основной теоремы?

Answer 1

Метод подстановки предлагает угадать решение, а затем доказать его по индукции.

Здесь мы угадываем частичное решение: T (2 ^ k) = k + 1

• Базовый случай: T (2 ^ 0) = T (1) = 1.
• Случай индукции для k> 0: T (2 ^ k) = T (2 ^ (k-1)) + 1 = k-1 + 1 + 1 = k + 1

Это дает нам, что T (n) = lg (n) + 1 для степени n, равной 2. Чтобы расширить это до полного В качестве решения пусть n 'будет наименьшей степенью 2, большей или равной n (для произвольного n> 0). Тогда T (n) <= T (n ') = lg (n') + 1. Поскольку n '<2n, имеем lg (n') <lg (2n) = lg (n) + 1. Итак, T ( n) <lg (n) + 2. </p>

Таким образом, мы доказали, что T (n) = O (lg (n)).

Answer 2

Это O(log₂(n)):

                    __
T(n)   = T(n/2) + 1   |
T(n/2) = T(n/4) + 1   | 
T(n/4) = T(n/8) + 1   |-- k operations
...                   |
T(1)   =          1 __|

n/2^k = 1  =>  n = 2^k  =>  k = log₂(n)   (by definition of log₂).

Answer 3

Многие стандартные рекуррентные соотношения могут быть легко решены с помощью теоремы магистра. У этого есть три случая.

Ваше рекуррентное отношение разрывается для случая # 2 с равными 1, b равными 2 и f (n) равными 1.