8.1 Lower Bounds for Searching Only by Comparisons of Keys
이 섹션에서는 키 비교만을 사용하여 배열에서 특정 키를 검색할 때 소모되는 최악의 경우 비교 횟수의 하한을 다룹니다.
특히, Binary Search와 Sequential Search의 의사결정 트리(Decision Tree)를 사용하여 검색 과정의 효율성을 분석합니다.
의사결정 트리 (Decision Tree)
• 정의:
의사결정 트리는 키 를 배열에서 검색하는 과정에서 발생하는 모든 비교를 나타냅니다.
• 각 내부 노드는 키 비교를 나타냅니다.
• 각 리프 노드는 검색 결과를 나타냅니다 (성공적으로 검색된 위치 또는 실패).
• 예시:
• Figure 8.1: 정렬된 배열에서 이진 탐색(Binary Search)의 의사결정 트리를 나타냅니다.
• Figure 8.2: 순차 탐색(Sequential Search)의 의사결정 트리를 나타냅니다.
검색 알고리즘과 의사결정 트리의 관계
검색 알고리즘이 개의 키를 처리한다고 가정할 때:
1. 개의 키를 검색하는 모든 알고리즘에는 유효한 의사결정 트리가 존재합니다.
2. 최악의 경우 비교 횟수는 트리의 최대 깊이 (트리의 루트에서 리프까지의 가장 긴 경로)로 표현됩니다.
8.1.1 Lower Bounds for Worst-Case Behavior
Lemma 8.1
Lemma 8.2
Theorem 8.1
8.1.2 평균 성능에 대한 하한 (Lower Bounds for Average-Case Behavior)
1. 정의와 개념
• 거의 완전 이진 트리(Nearly Complete Binary Tree):
• 한 이진 트리가 깊이가 d - 1 까지 채워져 있으면 “거의 완전 이진 트리”라고 합니다.
• 예를 들어, Figure 8.3(a)는 완전 이진 트리, Figure 8.3(b)는 거의 완전 이진 트리입니다.
• Binary Search의 결정 트리(Decision Tree)는 거의 완전 이진 트리로 나타낼 수 있습니다.
2. Lemma 8.3
내용:
• Binary Search의 결정 트리는 “거의 완전 이진 트리”입니다.
증명:
• 기초: 노드가 1개일 때, 이는 명백히 “거의 완전 이진 트리”입니다.
• 귀납 가정: 노드가 k 개일 때, 이진 트리가 “거의 완전 이진 트리”라고 가정합니다.
• 귀납 증명:
• 노드가 n 개일 때:
• n 이 홀수일 경우, Binary Search는 n - 1 /2로 두 서브트리를 나눕니다. 이 두 서브트리는 구조적으로 동일하며, 귀납 가정에 의해 거의 완전합니다.
• n 이 짝수일 경우에도, 좌우 서브트리 중 하나가 n/2 , 나머지가 (n/2) - 1 이며, 두 서브트리도 귀납 가정에 의해 거의 완전합니다.
• 따라서 결정 트리는 “거의 완전 이진 트리”입니다.
3. Algorithm 8.1: Binary Search 평균 시간 분석
기본 동작:
• x 와 S[{mid}] 의 비교.
분석:
4. Lemma 8.4
내용:
• TND 가 최소( minTND(n) )가 되려면 결정 트리가 “거의 완전 이진 트리”여야 합니다.
증명:
• TND 가 최소가 아닌 경우, 트리의 마지막 레벨에서 노드를 제거하고 위로 이동시켜 TND 를 줄일 수 있습니다.
• 따라서 minTND(n) 를 가지려면 트리가 “거의 완전 이진 트리”여야 합니다.
5. Lemma 8.5
내용:
• 평균 시간 복잡도는 \text{minTND(n)} / n 입니다.
증명:
• Binary Search의 평균 시간은 TND / n 에서 도출됩니다. Lemma 8.3과 8.4에 의해 이 결과를 얻을 수 있습니다.
6. Lemma 8.6
내용:
• 결정 트리에서 각 키 s_i 는 최소 한 번 비교되어야 하므로, 평균 시간 복잡도의 하한은 {minTND(n)} / n 입니다.
8.2 Interpolation Search
기본 개념
• Interpolation Search는 **키 값(key value)**이 균등하게 분포되어 있다고 가정할 때 Binary Search보다 효율적으로 동작할 수 있는 탐색 알고리즘입니다.
• Binary Search는 중간(mid) 위치를 항상 배열의 가운데로 설정하지만, Interpolation Search는 키 값의 분포에 따라 예상 위치를 계산해 중간값을 동적으로 결정합니다.
• 이를 통해 데이터가 균일하게 분포된 경우 Binary Search보다 적은 비교 횟수로 원하는 값을 찾을 수 있습니다.
8.3 Searching in Trees
이 부분은 트리 구조를 활용한 탐색에 대해 설명합니다. Binary Search(이진 탐색)와 Interpolation Search(보간 탐색)는 효율적이지만, 동적 데이터 추가나 삭제가 자주 이루어지는 경우에는 적합하지 않을 수 있습니다. 트리 구조는 이러한 상황에서 효율적인 해결책을 제공합니다.
8.3.1 Binary Search Trees (이진 탐색 트리)
1. 정적 탐색 vs 동적 탐색
• 정적 탐색: 데이터가 추가되거나 삭제되지 않고 고정된 경우. 이진 탐색(Binary Search)이 적합.
• 동적 탐색: 데이터가 자주 추가되고 삭제되는 경우. 이진 탐색 트리는 데이터 추가 및 삭제가 용이.
2. 이진 탐색 트리 구조
• 트리의 노드는 데이터 값을 저장하고, 왼쪽 자식은 더 작은 값, 오른쪽 자식은 더 큰 값을 저장.
• In-order Traversal(중위 순회):
• 왼쪽 서브트리를 탐색 → 루트 방문 → 오른쪽 서브트리 탐색.
• 이 방법을 통해 정렬된 순서로 데이터에 접근 가능.
3. 이진 탐색 트리와 이진 탐색의 관계
• 이진 탐색 트리에서 탐색 과정은 이진 탐색(Binary Search)와 동일.
• 예를 들어, 트리 구조에서 특정 값을 찾기 위해 키 값과 비교를 반복하며 좌우 서브트리로 이동.
4. 문제점
• 트리가 불균형(Skewed Tree) 상태가 되면 성능이 선형 시간 O(n)으로 저하될 수 있음.
• 예: 값이 정렬된 순서로 추가될 경우 트리가 리스트처럼 한쪽으로 치우침.
5. Theorem 8.3
• 평균적으로, 이진 탐색 트리를 사용하는 탐색 시간은 A(n) ≈ 1.38 \log n.
• 트리가 무작위로 구성된다고 가정하면, 효율적인 탐색 성능을 보장.
8.3.2 B-Trees (B-트리)
B-트리는 대규모 데이터베이스 및 외부 저장소 검색에서 주로 사용되는 트리입니다.
1. 특징
• B-트리는 항상 균형을 유지하며, 모든 리프 노드가 같은 깊이에 있음.
• 데이터를 추가하거나 삭제해도 트리의 균형이 깨지지 않음.
2. 3-2 트리 (3-2 Tree)
• 특성:
• 각 노드는 1개 또는 2개의 키를 포함.
• 키는 항상 정렬된 상태로 저장됨.
• 각 노드의 자식은 키 값에 따라 구분됨.
• 모든 리프 노드는 같은 깊이에 있음.
3. 추가 동작
• 키를 추가할 때:
1. 노드가 가득 차면, 가운데 키를 부모로 올림.
2. 리프 노드에 새 키를 추가하거나, 부모 노드로 분리.
4. 장점
• 항상 균형이 유지되므로 탐색, 삽입, 삭제 모두 O(\log n) 시간 복잡도를 가짐.
• B-트리는 대규모 데이터 처리에 적합하며, 대부분의 현대 데이터베이스 시스템에서 활용됨.
• Figure 8.5: 이진 탐색 트리의 구성 및 탐색 방법.
• Figure 8.6: 스큐드(Skewed) 트리 예시. 키가 정렬된 순서로 삽입될 경우.
• Figure 8.7: 3-2 트리에서 데이터 추가 예제.
• (a): 리프 노드에 새로운 키 추가.
• (b): 리프 노드가 가득 찬 경우 부모로 키 이동.
• (c): 루트 노드가 가득 찬 경우 새로운 루트 생성.
이렇게 B-트리는 데이터베이스 시스템에서 효율적으로 활용될 수 있는 매우 유용한 트리 구조를 설명합니다.
8.4 Hashing
Hashing 개요
Hashing은 키를 특정 값으로 변환하여 데이터를 효율적으로 저장하고 검색하는 기법입니다.
• 문제 상황: 1부터 100까지의 키와 약 100개의 데이터를 다룰 때, 배열에 데이터를 저장하면 키가 곧 인덱스가 되어 검색이 빠르지만, 메모리 낭비가 발생할 수 있습니다.
• 해결 방법: 키를 특정 범위(예: 0~99)로 변환하는 해시 함수를 사용해 메모리를 절약하면서도 효율적인 검색을 가능하게 합니다.
Hash Function
해시 함수 h(key) = key mod 100 는 키를 100으로 나눈 나머지를 반환합니다.
• 이 함수는 키를 특정 인덱스(0~99)로 변환하여 배열 S[i] 에 저장합니다.
• 조건: 키가 유일한 인덱스로 매핑되지 않을 가능성(충돌)이 존재합니다.
Collision (충돌)
• 충돌이란 두 키가 동일한 해시 값으로 변환되는 경우를 뜻합니다.
• 예를 들어, 키가 100개인 경우 충돌이 없는 확률은 매우 낮습니다 ( 9.3 * 10^{-43} ).
충돌 해결 방법: Open Hashing (열린 해싱)
• 각 해시 값에 버킷(bucket) 을 생성하고, 해당 해시 값에 매핑된 키들을 연결 리스트 형태로 저장합니다.
• 그림 8.8에서는 동일한 해시 값을 가지는 키들이 하나의 버킷에 저장된 예를 보여줍니다.
버킷과 검색
• 버킷 개수와 키 수: 버킷이 많을수록 충돌 확률이 줄어들지만, 메모리 낭비가 증가합니다. 일반적으로 키 수와 동일한 버킷을 사용하는 것이 적절합니다.
• 순차 검색: 충돌이 발생하면 연결 리스트를 순회해야 하므로 검색 시간이 증가할 수 있습니다.
Table 8.1
테이블 8.1은 k = \log n 또는 k = 2 \log n 일 때, 충돌 확률을 보여줍니다.
• 예를 들어, n = 1024 일 때 k = \log n 에 대해 충돌 확률은 0.00027 로 매우 낮습니다.
결론
• Hashing은 키가 균등하게 분포된 경우 Binary Search보다 훨씬 빠릅니다.
• 그러나 최악의 경우를 대비하여 해시 함수를 신중히 설계해야 합니다.
• 테이블을 참조하여 현실적인 키와 버킷 수에 따라 해싱 전략을 선택할 수 있습니다
8.5.1 Finding the Largest Key
1. 문제 정의:
• 주어진 배열 S 에서 가장 큰 키 \text{large} 를 찾습니다.
• 입력: n , 배열 S (크기 n ).
• 출력: \text{large} (가장 큰 값).
2. 알고리즘 (Algorithm 8.2):
void find_largest (int n, const keytype S[], keytype& large) {
index i;
large = S[1]; // 초기화
for (i = 2; i <= n; ++i) {
if (S[i] > large)
large = S[i];
}
}
• 배열의 각 값을 순회하며 현재까지 발견된 가장 큰 값과 비교해 업데이트합니다.
• 비교 연산 수: T(n) = n - 1 .
3. 이론적 최적성:
• 직관적으로, 배열의 모든 값을 비교해야 가장 큰 값을 찾을 수 있습니다.
• Theorem 8.7: 어떤 결정적 알고리즘이라도 모든 입력에 대해 n-1 번 이상의 비교를 수행해야 가장 큰 키를 찾을 수 있습니다.
• 증명: n-1 번보다 적게 비교하면 두 키를 비교하지 않아 잘못된 결과를 낼 수 있는 입력이 존재.
8.5.2 Finding Both the Smallest and Largest Keys
1. 문제 정의:
• 배열 S 에서 동시에 가장 큰 값 \text{large} 와 가장 작은 값 \text{small} 을 찾습니다.
2. 알고리즘 (Algorithm 8.3):
void find_both (int n, const keytype S[], keytype& small, keytype& large) {
index i;
small = S[1];
large = S[1];
for (i = 2; i <= n; ++i) {
if (S[i] < small)
small = S[i];
else if (S[i] > large)
large = S[i];
}
}
• 각 배열 요소를 순회하며 \text{small} 과 \text{large} 를 업데이트.
• 비교 연산 수: W(n) = 2(n-1) .
3. 향상된 방법:
• 한 번의 비교로 두 값을 동시에 판단하는 방식.
• Algorithm 8.4:
• 두 개씩 쌍을 이루어 비교. n/2 번의 비교로 \text{small} 과 \text{large} 후보군 생성.
• 추가 n/2 번의 비교로 최종 값 선택.
• 최적 비교 수: 3n/2 - 2 (짝수일 때).
Adversary Argument (대항 논증)
1. 목적:
• 알고리즘의 최악의 성능에 대해 하한선을 증명.
• 대항자가 알고리즘이 최대한 많은 비교를 수행하도록 설계된 입력을 동적으로 만듦.
2. 예제:
• n = 5 일 때, 8 번의 비교가 필요함을 대항자가 증명.
8.5.4 Finding the k-th Smallest Key
문제 설명
• 배열 S 에서 k -번째로 작은 키를 찾는 문제를 다룹니다.
• 단순히 배열을 정렬하고 k -번째 값을 반환하는 방법은 O(n \log n) 시간이 걸립니다.
• 더 적은 비교로 해결하기 위해 분할 및 정복(divide and conquer) 방법을 사용합니다.
알고리즘 설명 (Algorithm 8.5)
• Partition Procedure: 배열을 분할합니다. pivotpoint 는 기준 값입니다.
• pivotpoint 를 기준으로, 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 배치합니다.
• 재귀 호출:
1. 만약 k = pivotpoint , S[pivotpoint] 를 반환합니다.
2. k < pivotpoint : 왼쪽 부분 배열에서 다시 찾습니다.
3. k > pivotpoint : 오른쪽 부분 배열에서 다시 찾습니다.
시간 복잡도
• 최악의 경우: 모든 재귀 호출이 n-1 길이로 이어질 때, O(n^2) 시간이 걸립니다.
• 평균의 경우: 대부분 n/2 로 분할되므로 O(n) 에 가깝습니다.
Median of Medians (Algorithm 8.6)
개선 방법
• 분할 과정에서 pivot 을 임의로 선택하지 않고, Median of Medians 방법을 사용합니다.
• 배열을 5개씩 나눠서 각 그룹의 중간값을 찾습니다.
• 이 중간값들의 중간값을 구합니다(즉, “중간값들의 중간값”).
• 이를 기준으로 pivot 을 설정합니다.
알고리즘 수행 방식
1. 배열을 n/5 그룹으로 나눕니다.
2. 각 그룹의 중간값을 계산합니다.
3. 중간값들의 배열에서 다시 k번째 중간값을 찾습니다.
4. 이 값을 기준으로 분할합니다.
시간 복잡도
• 최악의 경우에도 O(n) 을 보장합니다.
• 이유: 매 재귀 호출마다 배열 크기가 n/5 로 감소하기 때문입니다.
Probabilistic Selection Algorithm (Algorithm 8.7)
확률적 접근법
• Sherwood 알고리즘: 분할 기준인 pivot 을 랜덤하게 선택합니다.
• 이 방식은 평균적으로 O(n) 시간에 동작합니다.
• 최악의 경우는 O(n^2) 이지만, 랜덤 선택으로 인해 발생 확률이 매우 낮습니다.
시간 복잡도 분석
• 기대값 계산을 통해 O(n) 임을 보입니다.
• 재귀적으로 기대값을 계산하며, 반복적으로 모든 가능성을 고려합니다.
'Book > Foundations Of Algorithms' 카테고리의 다른 글
| CH7. Introduction to Computational Complexity: The Sorting Problem (1) | 2024.12.05 |
|---|---|
| CH2_Exercise (0) | 2024.10.16 |
| CH1.Exercise (1) | 2024.10.14 |