私は今、問題セットに少し取り組んでおり、再発例のマスターメソッドをダウンさせたようです. ただし、他の方法 (再帰ツリー、置換) には問題があります。これが私が行き詰まっている質問です: T(n) = T(n-2) + n^2 次のようなパターンはありますか? n^2 + T(n-2) + T(n-4) +... n 個がなくなるまで続きます。したがって、n/2 回程度であり、n^2 + (n-2)^2 + (ni) ^2 ということで、漸近境界は theta(n^2) になりますか??
私は正直にここで暗闇の中で写真を撮っているので、誰かがこれらの質問に取り組む方法を教えてくれることを望んでいました. 質問への直接的な回答ではないかもしれませんが、どこから始めるべきかについてのヒントが最適です。
あなたが言ったように、結果は n^2 + (n-2)^2 + (n-4)^2 + ... になります。
直観的には、合計には (n/2) 個の要素があるため、O(n^2) 以上になることがわかります - 1 + 2 + 3 + ... + n が多いのと同じです。 O（n）よりも。
それを証明する 1 つの方法は、式があるすべての平方数の合計の半分で合計を近似できることです。シータ(n^3)です。
合計を結果にマッサージする方法は次のとおりです
n^2 + (n-2)^2 + ... + (n -2i) + ...
= {just writing in a different way}
(2n/2) + (2n/2 - 2)^2 + ... + (2n/2 -2i)^2 + ...
= {write m = n/2}
(2m)^2 + (2m-2)^2 + ... (2m - 2i)^2 + ...
= 4 ( m^2 + (m-1)^2 + ... (m-i)^2 ...)
= 4 ( sum (k^2) from k=1 to m)
= 4 ( sum (k^2) from k=1 to n/2)
= (n^3 + 3n^2 + 2n)/6
式を使用して