Arrays(배열), Binary Search(이진 탐색), 증명, 그리고 log

Arrays: 연속된 주소, 동일한 Type

장점: 각 원소에 대한 접근이 상수 시간에 가능. Search 가 빠름

단점: 배열의 크기를 변화하려면 비용이 크게 듦. Insert, Delete 가 느릴 수 있다.

-> 변화가 없거나 드문 형태의 자료에 사용한다.

 

Binary Search (이진 탐색)

자료의 탐색 알고리즘 중 선형 탐색(한 원소씩 처음부터 순차적으로 방문하여 찾는 방법) 보다 월등히 빠른 알고리즘으로, 자료를 반씩 나누어 탐색하는 알고리즘이다. 즉, 중간값을 보고 그보다 왼쪽에 있을지 오른쪽에 있을지 판단하여 그 해당 구역에서 새롭게 반씩 탐색하는 것이다. 이때, 자료는 (무조건) 정렬되어 있어야 한다. 

 

다음은 각각 반복적 절차와 재귀적 절차로 적성한 이진 탐색 코드이고, 각각에 대해 증명해보자.

int search(int a[], int n, int target){ // arrays a, length n, and target
	int left, right, middle;	// left, right, and middle elements of arrays a
    left=0; right=n-1;
    while(left <= right) { // repeat until the elements are flip
    	middle = (left + right) /2;
        if(a[middle]==target) return middle;
        else if(a[middle]>target) right=middle-1;
        else left=middle+1;
    }
    return -1; // there isn't target in array a
}

: Proof by Invariant : invariant* 가 사실이라는 것을 보이고, 그로부터 이 함수가 항상 성공한다는 것을 보이는 방법

 

1) invariant : 만약 어떤 i 에 대해서 a[i] == target 라면, left<=i<=right 가 항상 성립한다.

  -> 참! invariant 가 최초에 성립 && invariant 가 꺠질 수 있는 코드가 전혀 없다.

      (left, right 가 바뀌는 곳은 middle-1 or middle + 1 인데, 이는 invariant 를 깰 수 없다.)

2) a[i] == target 인 i 가 없다면 루프는 언젠간 반드시 끝나고 -1 을 리턴, i 가 있다면 루프 안에서 반드시 리턴 됨

 

* invariant : 항상 성립하는 사실. 프로그램이 돌아가는 동안 절대 바뀌지 않는 성질

 

int search(int a[], int n, int target){ // arrays a, length n, and target
	int middle, r;
    if(n==0) return -1;
    middle = n/2;
    if(a[middle]==target) return middle;
    else if(a[middle]>target) search(a, middle-1, target);
    else {
    	r = search(a+middle+1, n-middle-1, target);
        if(r==-1) return r;
        else return r+middle+1;
	}
}
    

: Proof by Induction with 수학적 귀납법

 

P(n) ; 만약 어떤 i 에 대해서 a[i] == target 이라면 i 를 리턴한다.

1) (Base) n=0 일 경우 어떤 i 에 대해서 a[i]==target 이 성립할 방법이 없고, 함수는 항상 -1 을 리턴

2) (Step) 

  - case 1: a[middle] == target 인 경우 middle 을 리턴하므로 주장이 성립

  - case 2: a[middle] > target 인 경우 a[middle], a[middle+1], ..., a[n-1] 중에서는 target 와 같은 값이 없다. 따라서 a[i]==target 인 경우가 있다면 i 는 0, 1, ... , m-1 중 하나이다. 귀납적으로 search(a, middle-1, x) 가 정확(성립)하다고 한다면 (P(n-1) 이 참이라고 귀납적으로 가정) 전체도 성립한다.

  - case 3: a[middle] < target : case 2 와 유사함

 

이 재귀 알고리즘의 Complexity 를 살펴보자.

T(n) = 1+ T(n/2)

      = 1 + 1 + T(n/4) = ... = log n

∴ T(n) = O(log n)

=> 빠른 속도!!!!!!!

 

log 란?

k=log2 n  <=> 2^k = n

따라서 log n 은

- 2를 몇 번 곱하면 n 이 되느냐

- n 을 2로 몇 번 나누면 1이 되느냐

의 답

다시 말해, n 이 계속 1/2 로 줄어드는데 log n 번만에 없어진다는 얘기!

 

log n 은 n 보다 월등히 작은데, n 이 10억이라면 log n 은 약 33 이기 때문이다.

 

log n 의 위력을 항상 기억하자. 

자료구조와 알고리즘에서 log n 을 설명하지 못한다면 공부를 제대로 한 것이 맞는지 의심해야 하기 때문이다.