找到T（n）= t（n - a）+ t（a）+ cn的基本情况

Question

我正在使用递归树方法解决重复： $$ t（n）= t（n - a）+ t（a）+ cn $$

当我开始解决时，我很容易结束： $ t（a）$ 将具有以下形式的成本计算：

$$ h * ca $$ 但我无法弄清楚如何解决基本案例。

我知道 $ t（na）$ t（na）$ 当 $ n= $ 。

但如何计算高度 $ h $ 的重复。 我知道基本情况可以定义为： $$ n-ia= 0 $$

我已经看到了本书中的前面的例子 inallithms介绍哪个引号：

在深度 $ i $ 中的子问题大小为 $ n / 4 ^ i $ 。就这样 子问题大小命中 $ n= 1 $ 当 $ n / 4 ^ i= 1 $ 或，等价度，当 $ i=log_4 n $

时

为复发： $ t（n）= 3t（n / 4）+ cn ^ 2 $

所以，来到那点是基本情况，使得子问题大小命中 $ n=？$ n=？$ 如上所述。

它是 $ n= $ ？

如果我错了，请纠正我。 谢谢。

Answer 1

每个 $ 0 \ le k \ le a $ 产生基本案例 $ t（k）$ 。 如果您尝试解决重复的大o，那么您也可能假设有一些 $ c $ 其中 $ t（k）\ le c $ 对于每个基本情况 $ k $ 。它将有助于使计算更容易