2. Divide and Conquer ㅣ분할정복법 ㅣKaratsuba 알고리즘

Divide and Conquer (분할정복법)

→ 원래 문제를 풀 수 있을 정도의 작은 크기의 부분 문제들로 분할해 각각 해결한 후, 부분 문제의 해답을 잘 모아 원래 문제를 해결하는 알고리즘으로서, 그 중 큰 정수 두개를 분할정복방법으로 곱셈하는 Karatsuba 알고리즘에 대해 다뤄보겠다.

---

일반적인 큰 두수 곱셈

→ n자리 수의 두 수를 곱셈하는 데 필요 한 기본 연산 횟수는,

   최대 n x n = n^2의 곱셈과 2n x n = 2n^2 의 덧셈으로, T(n) = 3*n^2, O(n^2)의 기본 연산 수행을 한다.

---

 

일반적인 곱셈보다 더 빠르게 곱셈하는 방법은 없을까?

---

분할정복 알고리즘을 고려하면, 큰 두수 u,v 의 곱셈을 아래와 같은 방식으로 나타낼수있다.

u = a^(n-1)....a^1 a^0

v = b^(n-1)....b^1 b^0 일때,

이 방식은, 두 n자리수의 곱셈 문제 1개를 (n/2) 자리수 곱셈 문제 4개로 분할 한 방식이다.

 

위 방식의 시간복잡도를 알아보자, (n = 2^k, T(1) = c)

T(n) = 4 * T(n/2) + cn

      = 4^2 * T(n/2^2) + 3cn

      = ....

      = 4^k * T(n/2^k) + cn(1+2+2^2+.....+2^(k-1))

      = O(4^k) = O(n^2)

 

시간복잡도는 O(n^2)로 일반적인 두 수의 곱셈의 시간복잡도와 같은 것으로 보아 시간 단축에는 큰 의미가 없어 보인다.

이때, Karatsuba알고리즘은 O(n^2)보다 더 효율적인 시간복잡도를 보여준다.

---

Karatsuba 알고리즘 (큰 정수 두개를 분할정복방법으로 곱셈하기)

→karatsuba는 위 분할식을 변형하여 두 n자리수의 곱셈 문제 1개를 (n/2) 자리수 곱셈 문제를 4개가 아닌 3개로 분할 하는 방식을 고안해냈다.

● karatsuba(x, y)

※Python Code 

def karatsuba(u,v) :

  if len(str(u)) == 1 or len(str(v)) == 1 :

    return x*y

  else :

    n = max(len(str(u)),len(str(v)))

    k = int(2 / n)

 

    a = int(x / 10**(k)) #x

    b = int(x % 10**(k)) #y

    c = int(y / 10**(k)) #w

    d = int(y % 10**(k)) #z

 

    ac = karatsuba(a,c)

    bd = karatsuba(b,d)

    ad_plus_bc = karatsuba(a+b,c+d) - ac - bd

 

    answer = ac * 10**(2*k) + (ad_plus_bc) + bd

    return answer

---

○ 코드 설명

△ 둘 중 하나라도 길이가 1(한자리 수)이면 두 수의 곱한 값을 반환한다.

△ 두 값중 긴 길이를 가진 수의 절반만큼 잘라 분할한다.

△ 재귀를 통하여 변수의 값을 구하고 최종 계산 값을 반환시킨다.

---

 

○ 시간 복잡도

 (n = 2^k, T(1) = c)

→T(n) =2 * T(n/2) + T(n/2 +1) + cn

 (위 n/2 +1은 (x+y)와 (w+z)가 가능한 최대 자리 수인 (2/n + 1)을 나타낸 것이며, 나온 식이며, O를 표현할때는 생략해도 무관하다.)

고로, T(n) =3* T(n/2) + cn

   O(n^2)보다는 확실하게 시간이 단축됨을 알 수 있다.

---

[출처]

신찬수 교수 (한국외국어대학교 컴퓨터 공학부), ‘알고리즘 - Algorithm with Python’, p.46~47

Youtube : ‘Chan-Su Shin’