✏️ 09/27 강의 필기

✔️ 순환함수의 장단점
[장점]
1) 문제 해결이 쉽다 (분할정복법 (Divide and Conquer))
2) 알고리즘 표현 및 이해가 쉽다

[단점]
1. 느리다 (이유: 중복계산)

• 동일한 비순환 알고리즘으로 변환하여 실행
  - 순환 <=> 비순환 전환은 언제든지 가능
• memory에 저장하여 반복 차단

🖇 Divide and Conquer(분할 정복법)
1. divide (분할) -> 동일한 유형의 작은 크기 문제(들)로 분할
2. conquer (정복) -> 분할된 문제들을 (서로 독립적으로) 각각 해결 (순환호출)
3. combine (병합) -> (각각 해결된) 작은 결과들을 종합하여 원래 문제의 답으로 정리

 ✔️ex1) Merge sort

A = [] //0~n-1
MS(0,n-1) //sorting 함수


MS(int l, int h) //l번째부터 h번째까지 h-l+1개의 데이터
{
	//순환호출이 무한으로 돌지 않도록 차단하는 장치
    if (h-l+1 <= 1) return 
    //(h-l+1 <= 1) == (h<=l) == 데이터의 개수가 하나 이하
    m = ⌊(l+h)/2⌋ //플로어함수: 나머지를 버리고 몫을 정수로 출력
    
	//두번의 순환호출
	MS(l,m)
    MS(m+1,h)
    Merge(l,m,h) //병합
}

✔️ 알고리즘 분석

M(n) = n개를 merge sort 하는데 걸리는 시간(=비교횟수)
	 = 0 	(if n<=1)
     = 2M(n/2) +n 	(if n>2) //함수 3개를 수행하는데 걸리는 시간
     
     	/*
     	MS(l,m)
    	MS(m+1,h)
    	Merge(l,m,h) 
        */

M(n) = 2M(n/2) +n
	 = 2[2M(n/4) +n/2] +n
     = 4M(n/4) + 2n
     = 4[2M(n/8) + n/4] +2n
     = 8M(n/8) +3n
     
     => 2^kM(n/2^k) + kn 
        (n/2^k 가 1이고, M(n/2^k)가 0이 될 때까지 반복)
	 = kn (n=2^k -> k = logn)
     = n * logn
     = O(nlogn)
     = Ω(nlogn) (최선)

• sorting 은 비교가 필수적인 알고리즘 -> 비교 기반 sorting