카라츠바의 빠른 곱셈 알고리즘

분할 정복 알고리즘의 한 예로, 재미있는 병합과정을 가진 알고리즘이다. 수 백 자리 이상의 큰 수의 곱셈할 때 사용하는 빠른 곱셈을 위해 만들어졌다. 기본적인 곱셈 방법 두 자연수의 십진수 표기가 배열에 주어진다고 할 때, 이 둘을 곱한 결과를 계산하는 가장 기본적인 방법은 아래 그림과 같다 이 과정을 코드로 곧장 옮깃 것이 아래와 같다 이 알고리즘의 시간복잡도는 두 정수 배열의 길이가 모두...

큰수의곱셈알고리즘카라츠바karatsubaalgorithmalgorithm