Algorithm, Data structure/Popular Algorithms 3

karatsuba algorithm

큰 수의 곱을 수행할 때 사용되는 karatsuba algorithm은 divide and conquer algorithm 을 통해 시간 복잡도를 줄인 algorithm 입니다.https://ko.wikipedia.org/wiki/카라추바_알고리즘 두 수의 길이가 an과 bn 이라 할 때 일반적인 곱셈법은 O(an*bn) 이라할 때 karatsuba algorithm은 두 수를 각각 반씩 나눠 네 개의 조각으로 만든 후 네 번의 곱을 세 번으로 줄여 시간 복잡도를 줄이는 방법을 사용했습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646..