알고리즘2 선택 정렬 증명

O(logN)

가장 대표적인 예 Recursive Binary Search

---

이 식은 사실이다.

 

*정확하게 고치자면 이렇게 표현해야 하지만 annotation으로 쓸 것이기 때문에 괜찮음

T(n) <= c(어떤 상수) + T(n/2)

 

---

Log란?

k = log n  <=>  2^k = n

2를 몇 번 곱하면 n이 되느냐의 질문에 대한 답

n을 2로 몇 번 나누면 1이 되느냐의 질문에 대한 답

(단계마다 반씩 버리면 답을 빨리 찾게 될 것 그리고 언젠가 찾게 될 것임!)

 

결국 O(log n)은 O(n)보다 훨~씬 작다.

 

---

선택 정렬

minimum을 찾고 바꿔주는 방식

sorting이 됐다는 증명은 어떻게 할 것인가?

 

---

*sorting 완료 후 다음을 만족해야 한다.*

조건1. { a[0], a[1], ..., a[n-1] } = { b[0], b[1], ..., b[n-1] }

(처음 배열을 a, 정렬 후 배열을 b라고 할 때)

집합에 새로 추가되거나 삭제되는 원소가 없어야 한다.

한 줄 한줄 코드를 보면 집합 조건을 깰 수 있는 부분이 없으므로 만족

조건2. b[0] < b[1]<...<b[n-1]

(편의상 같은 값은 없다고 가정)

 

---

 

*Proof by Invariant (loop를 도는 동안 변하지 않는 성질)*

k>=0 번째 루프가 끝난 후에 다음이 성립해야 한다.

 

 

이 시점에 Invariant 가 성립한다는 것을 의미한다. (*******)

알고리즘이 끝났을 때 k는 n이다. 따라서 n번째 루프가 끝났을 때,

 

Invariant (1).  a[0]<a[1]<...<a[k-1] 이 성립해야 한다.  (k>=0) 

a[0]<a[1]<...<a[k-1] => a[0]<a[1]<...<a[n-1] (조건2와 100%같음)

Invariant (2).  a[k-1] < a[x] (if k-1 < x)  

k-1 < x 인 조건이 없으므로 => 증명(2)는 그냥 사실임

 

 

조건1과 조건2을 만족했으므로 증명은 되었다.

---

 

*Prove Invariant by induction*

Invariant를 수학적 귀납법으로 증명할 것이다.

 

Base: k=0일 때,

(1)은 null condition, true

(2)도 null condition, true

 

 

Step: 

1)k번째 루프가 끝났을 때 Invariant(1)(2)가 성립한다면, (Invariant는 이제 그냥 믿으면 되는 사실!)

2)k+1번째 루프가 끝났을 때도 Invariant가 성립한다는 것을 증명해야 함 (코드를 통해 알 수 있음)

 

 

 

좀 더 자세히 설명하자면,

step1)

Invariant: k번째 루프가 끝났을 때 

(1)  a[0]<a[1]<...<a[k-1]  (k>=0)  
(2)  a[k-1] < a[x] (if k-1 < x) 

 

a[k], ..., a[n-1] 중 최소값을 a[k]로 옮겼음!!!!!!!

 

이 부등식 때문에 a[k]<a[x]라는 사실을 알 수 있다. (if x>k)

 

step2)

Invariant: k+1번째 루프가 끝났을 때 2개가 성립해야 한다.

(1)  a[0]<a[1]<...<a[k-1] < a[k] 
(2)  a[k] < a[x] (if k < x)  => 최소값을 옮겼기 때문에 성립

 

여기까지 원래 성립했던 사실임.

a[k-1] < a[k]  여기만 성립되는 것을 보여주면 step2가 바로 성립된다.

지금 a[k]는 a[x]중에 최소값을 옮긴 값이다. (x>k-1)

따라서 어떠한 a[x]보다도 a[k]는 큰 값이다. (x>k-1)

그렇다면 a[k+1]은 a[x]중에서 가장 큰 값이다. (x>k)