문제를 작은 문제 여러 개로 나누고, 작은 문제들을 먼저 푼 뒤 그 정답을 하나로 합친다.

Binary Search

정렬된 리스트에서 탐색 범위를 반으로 쪼개면서 찾아간다.

전체 탐색시간 T(n)이라 할 때 점화식을 다음과 같이 셍울 수 있다. T(n) = T(n/2) + O(1)

= T(n/4) + 2c = T(n/8) + 3c = … = T(n/2^i ) + ic, i=log n ⇒ T(1)+clogn = O(log n) 정리하면 T(n) = log n에 비례함을 알 수 있다. 즉 O(log n)이다.

Multiplication

n비트 이진수 x,y에 대해 xy를 계산할 때

• single-bit multiplication: O(1)
• single-bit addition: O(1)
• bit-shift: O(m)

보편적인 O(n^2) 방법은 다음과 같다.

그렇다면 DnQ를 이용해 빠르게 만들어 보자!

1. x와 y를 반으로 나눠서 곱하면 식을 다음과 같이 전개할 수 있다.

• 여기서 멈추면 그냥 그대로 n^2이 나온다.

1. 또한 xLyL, xRyR을 활용하기 위해 가운데 항을 다음과 같이 쪼갠다.