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 $ です。 。したがって、 SPAN CLASS="Math-Container"> $ n / 4 ^ i= 1 $ 、または等価的に、 $ i=log_4 n $

再発の場合： $ t（n）= 3t（n / 4）+ cn ^ 2 $

SO、上述の例のように、 $ n=？$ のような基本ケースになるのは、ポイントに到来します。

$ n= a $ ？

私が間違っているなら私を修正してください。 ありがとうございました。

Answer 1

$ 0 \ le k \ lea $ では、基本ケース $ t（k）$ 。 あなたが再発の大きなoを解決しようとしているならば、あなたはいくつかの $ c $ があると仮定することができます $ t（k）\ le c $ ごとに $ k $ 。それは計算を少し簡単にするのに役立ちます