Algorithm _#6 분할정복 알고리즘(2)

분할정복 알고리즘

ex) n자리 두 수의 곱셈

곱셈: 각 줄이 n번씩 곱하므로 n^2번 기본 곱셈

덧셈: 각 줄이 n번씩 더하고, A x B가 최대 2n자리까지 될 수 있으므로 2n x n = 2n^2번 기본 덧셈

=> 총 3n^2 기본 덧셈, 곱셈

=> O(n^2)시간 계산 가능!

u = -> a(n-1)~a(n/2) : x, a(n/2 + 1)~a0 : y

v = -> b(n-1)~b(n/2) : w, b(n/2 + 1)~b0 : z

=> u와 v를 각각 절반씩 나눠서 총 4개로 x,y,w,z로 분할

첫번째 줄은 xw, xz, yw, yz 4개의 곱셈으로 분할함

=> karatsuba는 두번째 줄처럼 xw, (x + y)(w + z) , yz 이 세 개의 곱셈으로 분할할 수 있음

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

= 3T(n/2) + cn

= O(n^(log3))

= O(n^(1.7….))

-> 분할정복 대표 알고리즘

def bs(A, a, b, k):
	if a > b: return -1
	m = (a+b)//2
	if A[m] == k: return m
	elif A[m] > k: return bs(A, a, m-1,k)
	else: return bs(A, m+1, b, k)

수행시간

T(n) = T(n/2) + c

(가정: n = 2^k)

T(n) = T(n/2^k) + (k-1)c

= kc

(k = logn)

= O(logn)

수행시간

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

= T(n/2^k) + c*(n/2^(k-1))

= cn( 1+ 1/2 + ... + 1/2^(k-1)) + c

= 2cn + c (밑줄부분이 2보다 작거나 같기 때문)

=O(n)

수행시간

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

-> cn이 k개 나옴

= kcn

= cnlogn

=O(nlogn)

수행시간

T(n) = 3T(n/2) + cn, T(1) = c

(n = 2^k 가정)

= cn(1+3/2 + 3^2/ 2^2 +… + (3/2^k)^(k-1)) + c* 3^k

= 2c x 3^k + c x 3^k - 2cn

= O(3^k)

= O(3^logn)

= O(n^log3)

= O(n ^1.5…)

(자세한 계산과정은 교재참고)