Algorithm _#5 분할정복 알고리즘

하한 (Lower Bound)

-> 최댓값 계산을 위한 비교횟수 하한 증명

def arrayMax(A):
	m = A[0]
	for i in range(1, len(A)):
		if m < A[i]: // n-1 번 수행
			m = A[i] // 입력값에 따라 다름
	return m

• 상한 : n - 1

• 하한: 토너먼트 형식으로 두 개씩 짝지어서 비교

악당과의 게임( adversary argument)

=> 알고리즘이 악당에게 x, y 비교 시키기 & 악당이 대답하면 다음으로 무엇을 비교할 지

• 값의 상태:
  • N: 한번도 비교되지 않은 상태
  • W: 항상 이긴 상태 (한번도 진 적 없음)
  • L: 최소 한번 이상 진 상태

• 최종상태:

  => W 1개( 최댓값 )

  => ★ L (n - 1)개 ★

• 이긴 것은 계속 이길 수 있게 배정

• 비교를 할 때 L은 최대 1개밖에 안 만들어짐

  => 최소 n - 1번 비교 반드시 필요!! (하한)

분할 정복법

: 큰 문제를 작은 문제로 분할해 재귀적으로 해결

1. 한 개를 나머지 전체와 비교

ex) 최댓값 찾기

​ max(A) = max(A[0], max[1: ])

• T(n) = T(n-1) + c, T(1) = c

  => T(n) = O(n)

2. 절반 나누기

ex) 최댓값 찾기

​ max(A) = max(max(A[ :4]), max(A[4: ]))

• T(n) = 2 T(n/2) + c, T(1) = c

  => T(n) = O(n)

3. 재귀호출

ex) 제곱

Power1(a,n):
	if n == 1: return a
	return a * power1(a, n-1)

• T(n) = T(n-1) + c, T(1) = c

  => T(n) = O(n)

Power2(a,n):
	if n == 1: return a
	if n == 0: return 1   			# a^0 = 1
	
	# a^n = a^(n/2) * a^(n/2) 
	
	if n % 2 == 0:		  			# n = 짝수			
    	return Power2(a, n//2) * Power2(a, n//2)
   
    else: return Power2(a, n//2) * Power2(a, n//2) # n = 홀수
	

• T(n) = 2T(n/2) + c, T(1) =c

  => T(n) = O(n)

Power3(a,n):
	if n == 0: return 1
	x = Power3(a, n//2)  # x = a^(n/2)
	if n % 2 == 0: return x * x
	else return x * x * a	

• T(n) = 2T(n/2) + c, T(1) = c

​ (n = 2^k 라 가정)

​ = T(n/4) +c + c

​ …=T(n/(2^k)) + kc

​ = k(c+1)

​ => T(n) = O(logn)

Fibonacci 수 계산 방법

• 점화식:

  F0, F1 : 주어짐

  Fn = F(n-1) + F(n-2)

• 수행시간:

  T(n) = T(n-1) + T(n-2)

• 방법 1

def fibo1(n) #return Fn
	if n == 0 or n == 1: return n
	return fibo1(n-1) + fibo1(n-2)

=> 중복적으로 호출함!

• T(n) = T(n-1) + T(n-2)

  =>

• 방법2 (행렬)

교재

• 리스트 => O(n)
• 두 변수 => O(n)