2. Divide-and-Conquer

493 ワード

Core

大きな問題をノドンのサブ問題(サブ問題間は互いに独立している)

に分ける.

各サブ問題を解決する

各サブ問題を統合する

Optimization Method

Reduce the sub Questionは代数によってサブ問題を解消する個数

XY = ?
X = A2^(n/2) + B
Y = C2^(n/2) + D
XY = AC2^(n/2) + (AD+BC)2^(n/2) + BD
AD+BC = (A-B)(D-C) + AC + BD

ACを通じて、BDは多重化された時間の複雑さ:

c    
W(n) = 4W(n/2) + cn 
W(n) = 3W(n/2) + cn

から

Pretreatment before inner Recursionは、前処理によって内部の再帰計算を減少する、実際には空間変換時間

である.
経典の例題.
高速ソートの実装