[알고리즘 분석] 1장. 효율, 분석, 그리고 차수 (2)

1. 순차 검색 알고리즘(Sequential Search)

- 문제: 크기가 n인 배열 S에 x가 있는가?
- 입력(parameter): 양수 n, 배열 S[1..n], 키 x
- 출력: x가 S의 어디에 있는지의 위치 (없으면 0)
- 알고리즘(자연어): x와 같은 아이템을 찾을 때까지 S에 있는 모든 아이템을 차례로 검사 -> x와 같은 아이템을 찾으면 S에서 위치를 리턴하고 모두 검사해도 찾지못하면 0을 리턴한다.

void seqsearch(int n, const keytype S[], keytype x, index& location){ //location: call by reference
    location = 1;
    while(location <= n & S[location] != x) // 찾지 못했을 경우
    	location++;
    if(location > n) // x가 S에 없을 경우
    	location = 0;
}​

- 최악의 경우 n개의 항목을 모두 검사해야함

 

2. 배열의 수 더하기

- 문제: n개의 수로 된 배열 S에 있는 모든 수를 더하라
- 입력: 양의 정수 n, 수의 배열 S[1...n]
- 출력: S에 있는 수의 합 sum

number sum(int n, const number S[]){
    index i;
    number result;
    result = 0;
    for(i = 1; i <= n; i++)
    	result += S[i]
    return result;
}​

 

3. 교환정렬

- 문제: 비내림차순(nondecreasing order)으로 n개의 키를 정렬하라
- 입력: 양의 정수 n, 키의 배열 S[1...n]
- 출력: 키가 비내림차순으로 정렬된 배열 S

void exchangesort(int n, keytype S[]){
    index i, j;
    for (i = 1; i <= n-1; i++)
    	for (j = i+1; j <= n; j++)
            exchange S[i] and S[j];
}​

 

4. 행렬 곱셈

- 문제: 두 개의 n x n 행렬의 곱을 구하라
- 입력: 양의 정수 n, 수의 2차원 배열 A[1...n] 와 B[1...n]
- 출력: A와 B의 곱이 되는 수의 2차원 배열 C[1...n]

void matrixmult(int n, const number A[][], const number B[][], number C[][]){
    index i, j, k;
    for (i = 1; i < n; i++)
    	for (j = 1; j < n; j++){
            C[i][j] = 0;
            for (k = 1; k <=n; k++)
                C[i][j] += A[i][k]*B[k][j];
      	}
}​

 

5. 이분검색 알고리즘(Binary Search)

- 문제: 크기가 n인 정렬된 배열 S에 x가 있는가?
- 입력: 양수 n, 배열 S[1...n], 키 x
- 출력: x가 S의 어디에 있는지의 위치 (없으면 0)

void binsearch(int n, const keytype S[], keytype x, index& location){
    index low, high, mid;
    low = 1;
    high = n;
    location = 0;
    while(low <= high && location == 0){
    	mid = (low + high) / 2;
        if (x == S[mid])
       	    location = mid;
        else if (x < S[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }
}​

- while문 수행할 때마다 검색 대상의 크기가 반씩 감소 -> 최악의 경우 lgn + 1개

 

6. 순차 검색(Sequential Search) vs 이분 검색(Binary Search) - 최악의 경우

배열의 크기(n)	순차 검색(n)	이분 검색(lgn + 1)
128	128	8
1,024	1,024	11
1,048,576	1,048,576	21
4,294,967,296	4,294,967,296	33