[알고리즘 분석] 도입

Algorithm 알고리즘

디자인 패러다임

Incremental approach: insertion-sort의 경우 A[1 ... j-1] 까지 정렬한 뒤 A[j] 번째 element를 제 위치에 넣는 방식을 사용함으로써 A[1 ... j] 까지 정렬된 subarray를 만들어 낸다.

Divide-and-conquer approach: 더 작은 크기의 문제로 나눈 뒤, 각각의 해결 방법을 combine 하여 원래의 문제로 돌아온다.

 

Divide-and-conquer 디자인 패러다임

Divide  문제를 더 작은 subproblem으로 나눈다.

Conquer  subproblem을 recursive하게 풀어 나간다.

Combine  subproblem의 해결 방법을 합쳐 나간다.

 

그 외의 디자인 패러다임

• Greedy
• 다이나믹 프로그래밍
• Branch and Bound
• Backtracking

---

Analysis 분석

Correctness & Efficiency

Correctness

Loop invariants: Loop를 돌려도 변하지 않는 성질(conditions and relationships)

 

Efficiency

Time complexity

Worst-case, Average-case, Best-case

 

Analysis of merge sort

Divide: 생략(trivial)

Conqure: 재귀적으로 2개의 subarray 정렬

Combine: Linear time merge

 

T(n) = 2 * T(n/2) + θ(n)

 

number of subproblems

subproblem size

dividing and combining time

 

T(n) = θ(1)                    if n=1

          2*T(n/2) + θ(n)      if n>1

 

 

master theorem(뒤에서 배움)으로 계산했을 때 T(n) = θ(n lg n) 임을 알 수 있다.