😘 기존의 곱셈 알고리즘
다음과 같은 과정은 배열([1,2,3,4])에 있는 각 항들에 대하여 모든 배열([5,6,7,8])들의 각 항에 대해 모두 비교하기 때문에 O(n2)과 같은 시간 복잡도가 소요된다.
😂 카리츠바 빠른 곱셈 알고리즘
카라츠바의 빠른 곱셈 알고리즘은 수백, 수만자리나 되는 큰 두개의 정수를 곱하는 알고리즘이다.
먼저 곱하려는 두 256자리 수 a,b가 있다고 있다.
그렇다면 a1,b1은 첫 128자리 그리고 그다음 128자리는 a0와 b0로 저장한다.
a = a110128 + a0
b = b110128 + b0
따라서 a*b는 다음과 같이 나타낼 수 있습니다.
a b = ( a110128 + a0) (b110128 + b0)
= a1 b1 10256 + (a1 b0 + a0 b1) 10128 + a0 b0
이때 카리츠바는
(a0 + a1) (b0 + b1) = a0 b0 + (a1 b0 + a0 b1) + a1 * b1
= z0 + z1 + z2
- z2 = a1 * b1
- z0 = a0 * b0
- z1 = (a0 + b1) * (b0 + b1) - z0 - z2
라는 사실을 발견하여 곱셈에 대한 식을 하나 줄이는 데 성공하게 되었다.
(두수를 곱하였을 때는 O(n^2)가 소요되지만 두수를 더할 때는 O(n)시간 만에 해결할 수 있다. 따라서 곱셈 식을 하나 줄였다는 것은 시간복잡도를 엄청나게 줄일 수 있다는 것을 의미한다. )
시간복잡도
카리츠바 알고리즘의 수행시간은 병합단계와 기저 사례 두 부분으로 나눌 수 있다. 병합단계에서 수행시간은 +,-의 수행시간에 지배되고, 기저 사례의 처리 시간은 (*)의 수행시간에 지배되는 것을 볼 수 있다.
(*) 수행시간
자릿수 n = 2k라고 할 때 재귀호출의 깊이는 k가 됩니다.
이때, 한 번 쪼갤 때마다 3번의 곱셈이 있었으므로 곱셈의 수는 총 3k 번 곱해집니다.
따라서 (*) 수행시간은 = O(3k ) = O(3lgn ) = O(nlg3 ) 이 됩니다.
(+,-) 병합 수행시간
단계가 내려갈 때마다 숫자의 길이는 절반으로 줄고 부분 문제의 개수는 세 배 늘기 때문에, i번째 단계에서 필요한 연산 수는 이 함수는 nlg3과 같은 속도로 증가합니다. 따라서 카리츠바 알고리즘은 곱셈이 지배하며, 최종 시간 복잡도는 O(nlg3 )이 됩니다.
- 주의사항
카리츠바 알고리즘은 상당히 복잡하기 때문에 입력의 크기가 작을 경우 O(n^2)보다 느린 경우가 많다.
def kara(a,b):
if len(str(a)) == 1 or len(str(b)) == 1:
return a*b
else:
n = max(len(str(a)),len(str(b)))
k = n // 2
a1 = a // 10**k
a0 = a % 10**k
b1 = b // 10**k
b0 = b % 10**k
a1b1 = kara(a1,b1)
a0b0 = kara(a0,b0)
a1b0_plus_a0b1 = kara(a0+a1,b0+b1) - a1b1 - a0b0
result = a1b1 * pow(10,k*2) + a1b0_plus_a0b1 * pow(10,k) + a0b0
return result
a = kara(1234,5678)
print(a) 