자료구조 시작 전 알기 (5) Arrays, Algorithms, Complexity, and Recursion

본격적으로 자료구조를 살펴보자. 첫번째로 살펴볼 자료구조는 프로그램 언어를 하나라도 배운 사람이면

이숙한 그 이름 배열이다. 배열에 대해 정리하면 다음과 같다.

 

 # Array ( 배열 )

• 정의 : 연속된 주소, 동일한 Type
• 장점 : n개 중 k번째 access(Read&Write)가 상수 시간에 가능, Search(어떤 x가 배열안에 있느냐?)가 빠름
• 단점 : 크기 변화 비용이 크다. Insert, Delete가 느릴수 있따.
• 사용 : 변화가 없거나 드문 자료

5

3

7

6

4

8

12

 

이런식으로 연속된 주소에 동일한 타입을 주르륵 붙여 놓은 자료구조이다.

 

이제 이 배열을 통해서 Binary Search 의 정확성과 속도를 알아보자.

 

보통  Binary Search의 코드는 다음과 같이 작성될 것이다. (정확한 코드는 아니지만 흐름은 다음과 같다.)

 

int search(int a[], int n, int x)
{
    int l, r, m;
    l=0; r = n-1;
    while (l <=r) {
        m =(l+r)/2;
        if (a[m] ==x) return m;
        else if (a[m] > x) r =m-1;
        else l = m+1;
    }
 
    return -1;    
}

a는 입력 배열이고 정렬되어있다고 가정한다. n은 배열의 사이즈를 뜻한다 ( index : 0~n-1 )

l은 검색 범위의 왼쪽 끝이고, r은 검색범위의 오른쪽 끝이다. ㅣ,r, 이 index가 되는 것이다.

while (l <=r) 는 r 이  l 보다 크다는 뜻은 배열 안에 원소가 없다는 뜻과 같다. 배열에 원소가 없으면

찾아볼 이유가 없으므로 다음과 같은 조건 안에서만 실행한다.

m 은 ㅣ과 r의 중간 값이다.

그다음에 어떠한 값이 배열 안에 들어있으면(값을 찾았으면) 인덱스(m)를 배출하도록 한다.

a[m] 이  찾으려는값 X 보다 크다는 것은 무슨 뜻이 되겠는가? X는 a[m]의 왼쪽에 위치 한다는 뜻이다.

(a 가 이미 정렬된 배열이므로) 그럼 왼쪽 배열만 찾으면 되므로 다시 앞의 과정을 반복하면 된다.

 

 

그럼 Binary Search는 어떤 식으로 증명하면 될까?

 

Proof by Invariant

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

  • Invariant는 최조에 성립하고, invariant가 깨질 수 있는 코드가 전혀 없다.

•  a[i] = x 인 i가 없다면 루프는 반드시 끝나고 -1이 리턴 됨
•  a[i] = x 인 i가 있다면 루프 안에서 반드시 리턴 됨

 

invariant는 불변성(절때 변하지 않는)을 뜻한다. 그 성질에 대해서 항상 성공한다고 증명이 가능하다.

 

재귀적으로도 Binary Search 코드를 짤 수 있을까? 

int search(int a[], int n, int x)
{
    int m;
    if (n == 0) return -1;
    m = n/2;
    if (a[m] == x) return m;
    else if (a[m] > x) return search(a, m-1, x);
    else {
    r = search (a+m+1, n-m-1, x);
    if ( r == -1) return -1;
    else return r+m+1;
}

search 의 입력값은 위의 코드와 같고

6번째 줄은 n 이 0 일때는 답이 없으니 -1을 리턴한다.

n이 0이 아니면 n/2 를 m에 넣는다.

8번째 줄은 정답일 경우 인덱스를 리턴하는 것이다.

9~11 번째 줄이 인덱스를 더하는 것 때문에 조금 복잡하게 되었다. 

Proof by Induction

• 주장 : 만약 어떤 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 중 하나이다. 귀납적으로 search(a, m-1, x) 가 정확하다고 가정하면 즉 ,제일 위 주장이search(a, m-1, x) 에서 성립한다고 가정하면 제일 위 주장이 성립함. 
  • case3:  a[m] < x 인 경우 a[0], a[1], a[2], ... ,a[m] 중에서는 x와 같은 값이 없다. 따라서 a[i] = x 인 경우가 있다면 i는 m+1, m+2, ... , n 중 하나이다. 귀납적으로 search(a, m-1, x) 가 정확하다고 가정하면, search(a+m+1, n-m-1, x)도 성립하고, 제일 위의 주장이 성립함.

 

 

Binary Search 의 시간 복잡도를 따지면 다음과 같다.

The Complexity

 

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

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

따라서 T(n) = O(log n) 

 

 

정확하지는 않지만 재귀 함수를 보면 if (a[m] == x) return m; 까지 돌아가는데 1이라고 가정하면,

1이 아니면 n/2에서 재귀호출을 하기 때문에 계속해서 돌아가면 결국 log n 에 수렴하게 된다.

 

** What is Log ?

• k = log n <=> 2^k( 2의 k승 ) = n
• 따라서 log n은
  • 2를 몇번 곱하면 n이 되느냐의 질문에 대한 답
  • n을 2로 몇 번 나누면 1이 되느냐의 질문에 대한 답
• log n 은 n보다 월등히 작다.
  • log n  = 10, n =1024
  • log n  = 20, n = 1048576
  • log n  = 30, n = 1073741824

간단한 알고리즘을 정확하게 증명하는 법을 알아보았다. 앞으로 이 기법으로 많은 알고리즘을 분석하는 시간을 가지게 될것이다. 다음 포스터에서는 다른 정렬법의 내용을 다루어 보겠다.