Найти базовый чехол для t (n)= t (n - a) + t (a) + cn

Question

Я решал рецидив, используя метод рекурсионного дерева: $$ t (n)= t (n - a) + t (a) + cn $$

Когда я начал решать, я мог легко сделать тот факт, что $ t (a) $ будет иметь общий расчет затрат в виде:

$$ h * ca $$ Но я не мог понять, как решить базовый случай.

Я знаю, что $ t (na) $ будет в базовом случае, когда $ n= A $ .

Но как вычислить высоту $ h $ рецидива. Я знаю, что базовый случай можно определить как: $$ n-ia= 0 $$

Я видел предыдущие примеры в книге Введение в алгоритмы , какие цитаты:

Размер подгруппы для узла на глубине $ i $ $ n / 4 ^ i $ Отказ Таким образом Размер подблема удается $ n= 1 $ Когда $ n / 4 ^ i= 1 $ или, эквивалентно Когда $ i=log_4 n $

Для рецидива: $ t (n)= 3t (n / 4) + cn ^ 2 $

Итак, приходя к тому, что будет базовый случай, такой, что размер подзаготовления попадает в $ n=? $ , как в приведенном выше примере. .

Будет ли это $ n= a $ ?

Пожалуйста, поправьте меня, если я ошибаюсь. Спасибо.

Answer 1

Каждый $ 0 \ le k \ le a $ дает базовый случай $ t (k) $ Отказ Если вы пытаетесь решить Big-O рецидива, то вы также можете считать, что есть некоторые $ C $ Где $ T (k) \ le c $ для каждого базового случая $ K $ .Это поможет сделать вычисление немного легче