[컴퓨터알고리즘] 1. Analysis of Algorithms
TEXTBOOK - [Introduction to Algorithms]
2.1 Insertion sort - 삽입정렬
+자료구조
삽입정렬은 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드가 들어오면 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리에 삽입함으로써 정렬을 유지한다. 이와 같은 작업을 카드 수 만큼 반복하면 전체 카드가 정렬된다.
pseudo코드
Insertion-sort(A,n) >A[1...n]
1. for j<-2 to n
2. do key <-A[j]
3. i<- j-1
4. while i>0 and A[i]>key
5. do A[i+1] <-A[i]
6. i <- i-1
7. A[i+1]=key1. 인덱스 2부터 시작한다. 인덱스 1은 이미 정렬된 것으로 볼 수 있다.
2. 현재 삽입될 숫자인 j번째 정수를 key 변수로 복사한다.
3. 현재 정렬된 배열은 j-1까지이므로 j-1부터 역순으로 조사한다
4. i값이 0보다 크고 key 값보다 정렬된 배열에 있는 값이 크면
5. i번째를 i+1번째로 이동한다.
6. i를 하나 감소한다.
7. i번째 정수가 key보다 작으므로 i+1번째가 key 값이 들어갈 위치이다.
Correctness 정확성
input값이 이미 정렬되어있거나 반복되는 요소를 포함하더라도 sorting이 항상 성립해야함
optimization과 같이 최적을 찾는 solution에서는 명백하지 않다
How to prove correctness
counter example 반례증명
-모든 작은 예시
-매우 크거나 작은 값 등등 생각
*반례를 찾지 못했다고 해서 이 알고리즘이 정확한 것은 아님
Loop invariants
[증명 by induction(귀납법)]
주장 - S(n)은 n>=1인 모든 n에 대해 참이다
초기 조건 - n=1일때 참임을 보인다
귀납적 가설 - 임의의 k에 대해 n=k일때 참임을 가정
증명(show) - n=k+1일때 참임을 보여라
Initialization(basis) 초기조건 - 루프불변성은 루프의 첫 반복 전에 참이다
Maintenance 유지조건 - 루프 반복전에 참임을 가정하고(귀납적 가설) 다음 반복전에 참이 유지되는지 보여라 (증명)
Termination 종료조건 - 루프가 종료될 때 루프 불변성은 알고리즘이 정확성을 보여주는 유의미한 특성이 있음을 보여라
Insertion-sort(A,n) >A[1...n]
for j<-2 to n
do key <-A[j] //A[1]은 정렬되어있으므로 초기 조건을 만족 //반복 j이전에 참이라 가정
i<- j-1
while i>0 and A[i]>key
do A[i+1] <-A[i]
i <- i-1
A[i+1]=key //j+1 반복 전에 참이다
2.2 Analazing algorithms
Efficiency
Correctness만으로 충분하지 않음
How to measure complexity
-> Machine-independent : RAM(random-access machine) model
Asymptotic Analysis 점근적 분석
running time 은 input의 size에 의존적이다
큰 배열은 정렬에 더 많은 시간을 필요로 한다
input의 크기가 n일때 걸리는 시간을 T(n)이라 하면
n이 무한히 커질때 T(n)을 보는 것
차수가 클때 증가하는 input size n에 더 지배적이다
Insertion sort의 running time
이미 정렬되어있거나 길이가 짧으 정렬이 더 쉽다
guarantee를 위해 upper bounds(상한)을 찾아야함
분석의 종류
- worst-case : maximum time
내부 루프문의 실행 = an^2 +bn+c
- average-case : expected time
내부 루프문의 실행 = an^2 +bn+c
- best-case : fast on some input
-이미 정렬 되어있을때
내부 루프문이 실행될 필요 없음 = an+b
1 << logn << n << nlogn << n^2 << n^3 << 2^n << n!
2.3 Designing algorithms
Recursive algorithms
큰 문제를 작은 것으로 divide 하고 작은 문제를 재귀적으로 혹은 명시적으로 해결한 루 이 해결책을 결합해 본래의 문제를 해결하는 방법 --> devide and conquer 분할 정복 기법
Merge sort 합병 정렬
MERGE-SORT A[1 .. n]
1. IF n=1, done
2. Recursively sort A[1 ..⌈n/2⌉] and A[⌈n/2+1 .. n⌉]
3. Merge the 2 sorted lists
Recursive algorithm 의 correctness
귀납법에 의해
1. 초기 조건 - 작은 예시에 만족함을 증명
2. 귀납적 가설 - 모든 sub 문제들의 정확성을 가정
3. 단계 - 귀납적 가설이 맞다면 본래의 문제의 정확성을 보여라
Correctness of merge sort
MERGE-SORT A[1 .. n]
1. IF n=1, done
2. Recursively sort A[1 ..⌈n/2⌉] and A[⌈n/2+1 .. n⌉]
3. Merge the 2 sorted lists
=>>
1. 초기조건 - n=1이면 A[1 ..1]은 이미 정렬되어있기때문에 correct answer
2. 귀납적 가설 - A[1 ..⌈n/2⌉] and A[⌈n/2+1 .. n⌉] 이 correctly sorts라 가정
3. 단계 - 전체 배열 A[1 ..⌈n/2⌉] 과 A[⌈n/2+1 .. n⌉] 은 합병 후에 정렬된다
Recurrence for 합병 정렬