| 분할과 정복 개념 | 분할과 정복 사례 |

분할과 정복 사례

■ 큰 정수의 곱셈

N자리 2개의 양의 정수 X, Y의 곱셈 수행시간은 θ(N²)이다.

X = 61,438,521 이고, Y = 94,736,407 이면 XY = 5,820,464,730,934,047

X, Y를 2등분하여 X_L = 6,143  X_R = 8,521  Y_L = 9,473  Y_R = 6,407이라면

X = X_L10⁴ + X_R 이며, Y = Y_L10⁴ + Y_R 이다. 즉, 다음 식이 성립한다.

          XY = X_LY_L10⁸ + (X_LY_R + X_RY_L)10⁴ + X_RY_R    ----------------------   (1) 

식 (1)의 수행시간 : 4번의 N/2자리 곱셈과 O(N)번의 덧셈, 즉

         T(N) = 4T(N/2) + O(N)   ――――――――> O(N²)   ----------------------   (2) 

식 (2)에서 N/2자리 곱셈 4번을 N/2자리 곱셈 3번으로 대체가능

          X_LY_R + X_RY_L = ( X_L - X_R )( Y_R - Y_L ) + X_LY_L + X_RY_R  ---------------   (3) 

식 (3)에서 X_LY_L 과 X_RY_R 은 식 (1)에서 이미 계산한 것이다. 

따라서 ( X_L - X_R )( Y_R - Y_L ) 의 N/2자리 곱셈 한 번만 추가하면 된다.

즉, T(N) = 3T(N/2) + O(N)  ――――――――> O(N^log3) = O(N^1.59)  --------------   (4)