algorithm - T（n）= 4T（n / 2）+n²を解く

Question

置換法を使用して再発を解決しようとしています。漸化式は次のとおりです。

T（n）= 4T（n / 2）+ n ²

私の推測では、T（n）はΘ（nlogn）であり（マスター定理のためにそれについて確信しています）、上限を見つけるために、誘導を使用します。T（n）<= cn ² lognであることを示しようとしましたが、機能しませんでした。

T（n）<= cn ² logn +n2^を取得しました。次に、T（n）<= c ₁ n ² logn-c ₂ n ²の場合、それもO（n ² logn）であることを示しようとしましたが、それも機能せず、T（n）を取得しました。 <= c ₁ n ² log（n / 2）-c ² _n 2 ⁺ n2` 。

この再発をどのように解決できますか？

Answer 1

T(n) = 4T(n/2) + n 2 
     = n 2 + 4[4T(n/4) + n²/4]
     = 2n 2 + 16T(n/4)
     = ...
     = k⋅n 2 + 4 k T(n/2 k )
     = ...

に達するとプロセスは停止します。 ⇒ ⇒2kn
k = log2n
T(n) = O(n2logn)

Answer 2

非再帰的な形式で方程式を書き換えることができます

再帰方程式は非常に単純です。T(n/2) を展開するたびに、新しい項が 1 つだけ表示されます。したがって、非再帰形式では、二次項の合計が得られます。A(n) が であることを示せばよいだけですlog(n)(簡単な演習として残します)。