Karatsuba's Algorithm (1) 썸네일형 리스트형 56. Karatsuba's Algorithm 두 정수의 곱을 구할 때, 곱한 결과가 일반적인 정수 자료형에 저장하기에는 너무 큰 경우 정수를 문자열 형태로 저장한 후 직접 곱셈을 구현해야 한다. $100\text{~}1000$자리 정도의 정수를 곱할 때는 일반적인 $\Theta(n^2)$ 곱셈을 구현해도 괜찮지만 자릿수가 $10000$ 단위가 되면 $\Theta(n^2)$ 곱셈은 속도가 많이 느려지게 된다. 이때 카라츠바 알고리즘(Karatsuba's Algorithm)을 이용하면 곱셈의 시간복잡도를 $\Theta(n^{\text{lg }3})$으로 줄일 수 있다. 카라츠바 알고리즘은 분할 정복을 이용하여 정수의 곱을 계산하는 과정에서 중복된 계산을 유도한다. 계산이 중복되면 한 번만 해도 되므로 그만큼 연산 횟수가 줄어들게 된다. 곱해야 하는 두.. 이전 1 다음
