algorithm - 分割して征服する と 減算して征服する の違いは?

Question

再帰について読んで、再帰方程式を解いています。「減算して征服する」という用語に出くわしました。「分割統治法」との違いは? 分割統治法 (マスター定理や再帰ツリーなど) の再帰方程式を解くために使用されるのと同じ手法を使用して、この種の問題を解決できますか?

Answer 1

「マスター定理は、分割統治アルゴリズムに適用されます。一部のアルゴリズムは、T(n) = aT(nb) + Θ(nd) の形式の反復につながります。これらは、「減算統治」または「巨大なステップ、ベイビーステップ」と呼ばれる場合があります。 「アルゴリズム」。

実は引き算は割り算と違い、サブ問題のサイズが割り切れず、引き算以外は同じです。

詳細については、このリンクを確認してくださいhttp://www.eecis.udel.edu/~saunders/courses/621/11s/notes/notes/Master-theorem.html

Answer 2

「分割統治法」アルゴリズムについて読んだところ、二分探索を例として使用した「減少統治法」に出くわしました。したがって、「減算と征服」は「減少と征服」に関連していると思います。ここでは、サブ問題を結合して最終的な解決策を見つけるのではなく、元の問題の残りの部分を無視して、サブ問題自体から解決策を見つけます。