[Lecture] Sum, Binary Search, Selection Sort

A Simple Code & A Simpler Code

일반적인 코드

재귀를 사용한 코드

 

첫번째 그림: 일반적으로 누적합을 구할 수 있는 코드

두번째 그림 : 재귀로 누적합을 구할 수 있는 코드

 

두번째 그림의 코드가 맞는지 증명해보자

 

수학적 귀납법 : sum(x)는 1+2+...+x를 항상 리턴한다

 

base: P(1) 즉, 코드에 1을 넣었을 때 return값은 1이다 

따라서 sum(1)이 리턴하는 값은 1임을 알 수 있다

 

step: 코드를 보면 sum(x)는 x+sum(x-1)의 값을 리턴한다

sum(x-1)의 리턴값은 1+2+...(x-1)와 같다고 할 때, sum(x)는 1+2+....+x를 리턴한다는 것을 확인할 수 있다

 

 

 

---

Binary Search & Recursive Binary Search

시간 복잡도 : O(n) (첫번째 코드)

시간 복잡도 : O(logn) (두번째 코드)

 

Proof by Invariant

Invariant : 만약 어떤 i에 대해서 a[i] = x라면 l <= i <= r이 항상 성립한다

a[i] = x인 i가 없다면 루프는 반드시 끝나고 -1이 리턴된다

a[i] = x인 i가 있다면 루프 안에서 반드시 리턴된다

 

주장 : a[i] = x인 i가 있다면 루프 안에서 반드시 리턴된다

base : n = 0인 경우 어떤 i에 대해서 a[i] = x가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다

step: 

case 1 : a[m] = x인 경우 m을 리턴하므로 주장이 성립한다

case 2 : a[m] > x인 경우 a[m], a[m+1],.....a[n] 중에서는 x와 같은 값이 없다. 따라서 a[i] = x인 경우가 있다면 i는 0,1,...m-1 중 하나이다. (a[m]<x에 있다고 확신할 수 없음) 귀납적으로 search(a,m-1,x)가 정확하다고 가정하면, 위 주장이 성립한다

case 3 : a[m] < x인 경우 a[0], a[1],.....a[m] 중에서는 x와 같은 값이 없다. 따라서 a[i] = x인 경우가 있다면 i는 m+1,m+2,...n 중 하나이다. (a[m]>x에 있다고 확신할 수 없음) 귀납적으로 search(a+m,n-m,x)가 정확하다고 가정하면, 위 주장이 성립한다

 

+r이 l보다 작아지면, l부터 r까지 있을 때 0개 중에 x가 있다는 말이고, 이건 x가 없다는 말과 같은 것이다

---

Selection Sort

시간복잡도 : O(n^2)

 

Sorting이 됐다는 것을 어떻게 증명할까?

입력 : a[0], a[1], ... , a[n-1] (정수집합)

Sorting이 완료된 후 다음 조건을 만족해야한다

 

1. 값이 덮어써지거나, 새로 써지면 안된다 기존의 집합 원소가 유지가 되어야한다 (코드 내에서 교환만 일어나기 때문에 조건1은 절대 깨지지 않는다)

2. sorting이 끝난후 배열에 저장된 값들은 크기관계가 존재해야한다 (편의상 같은 값은 없다고 가정한다)

 

Proof by Invariant

집합 조건을 깰 수 있는 코드는 없다

Invariant : k번째 루프가 끝난 후에

(1) a[0] < a[1] < .. < a[k-1] -> a[0] < a[1]<...<a[n-1] //0 ~ k-1까지 sorting되어있다

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

알고리즘이 다 끝났을 때는 n번째 루프가 다 끝났을 때이다 x>n-1보다 큰 배열은 없다

따라서 이건 trivial true(vacuous true)이다

 

base : k = 0, (1)은 null condition, true (2)도 null condition, true이다

k가 0일 때, a[-1]까지 이므로 아무것도 하지 않았다 = 0번째 루프를 돈다는 뜻 (아무것도 X : vacuous true)

step : k번째 루프가 끝났을 때 Invariant가 성립한다면, k+1번째 루프가 끝났을 때도 Invariant가 성립한다

 

Invariant : k번째 루프가 끝난 후에

(1) a[0] < a[1] < .. a[k-1]

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

a[k].. a[n-1] 중 최소값을 a[k]라로 옮긴다 (k~n-1)

Invariant : k+1번째 루프가 끝난 후에

(1) a[0] < a[1] < .. a[k-1] < a[k]

(2) a[k] < a[x] if x > k

 

Recursive Selection Sort

시간 복잡도 : O(n^2)

 

집합조건을 깰 수 있는 코드는 없다

base : n = 1 할 일이 없다

step : n-1일 때 sort() 함수가 성공한다면 (즉, 재귀호출이 끝난 후 a[1] < a[2] < ...< a[n-1]라면)n일때 sort()함수가 성공한다

(함수가 끝날때 a[0] < a[1] < a[2] < ... < a[n-1]이 성립한다)

코드에서 a[0]이 가장 작은 수라는 것을 확인할 수 있다

재귀호출 전 a[0] < a[1], a[0] < a[2],....이므로 함수가 끝날 때  a[0] < a[1] < a[2] < ... < a[n-1]이 성립한다