최선, 최악, 그리고 평균의 경우
 |
컴퓨터 과학분야에서, 주어진 알고리즘의 최선, 최악, 그리고 평균의 경우(best, worst, and average cases)는 각 최소, 최대, 평균 자원의 사용량을 의미한다. 보통 여기서 고려하는 자원은 실행시간 (예, 시간 복잡도:time complexity), 메모리 또는 기타 다른 자원들이다.
최악의 경우 알고리즘이 항상 제시간 안에 끝나는 것을 보장하기 위하여 얼마의 시간 걸리는지 아는 것은 중요하다. 그렇기 때문에 실시간 연산시 최악의 실행 시간은 중요 고려사항이 된다.
알고리즘 분석시 평균 성능과 최악의 경우 성능이 가장 많이 활용된다. 최선의 경우 성능은 가장 적게 활용되나 때때로 유용하게 사용된다. 예를 들어 개별 작업의 최선의 경우 성능을 알고있다면, 이를 통해서 전반적인 최악의 경우 분석의 정확도를 향상 시킬수 있다. 예상 실행 시간을 계산하기 위하여 컴퓨터 과학자들은 확률적 분석 기술들을 사용하며, 특히 기대값(expected value)을 활용한다.
이 용어들은 다른 문맥에서 활용된다; 예를 들어 최악/최선의 전염병 확산 결과, 전자 회로가 방출하는 최악의 경우 온도 등. 특정 내성 요소들이 사용되는 곳에서, 장비들은 최악의 경우 내성과 외부 조건 안에서 적절히 작동하도록 디자인 되어야 한다.
알고리즘의 최선의 경우 성능[편집]
용어 최선의 경우 성능(best-case performance)은 전산학에서 최적조건 하에 알고리즘의 동작을 묘사하는데 사용된다. 예를 들어, 리스트(list)의 간단한 선형 탐색 문제에서 최선의 경우는 원하는 원소가 리스트의 처음에 위치하는 경우이다.
알고리즘 선택 및 개발에 있어 최선의 경우 성능은 거의 활용되지 않으며, 대부분 평균 경우 복잡도(average-case complexity)와 최악의 경우 성능(worst-case performance)의 향상에 관심이 있다. 유한 입력 집합의 하드-코딩(hard-coding) 해결법으로 좋은 최선의 경우 실행 시간을 가지도록 알고리즘을 수정한다.[1]
최악의 경우 대 평균 경우 성능[편집]
최악의 경우(worst-case) 성능 분석과 평균 경우 성능 분석은 서로 유사성을 가지지만, 두 가지 분석을 위해서 실제로 다른 도구와 접근법이 요구된다.
평균 입력이 무엇인지 정의하는 것은 어렵고, 흔히 평균 입력은 수학적으로 특징 짓기 어려운 특성을 가진다. 예를 들어 문자열 연산을 위한 알고리즘 역시 평균 입력을 정의하기 어렵다. 심지어 특정 “평균 경우(average case)”의 합리적인 기술이 가능하더라도, 이를 분석하기 위하여 매우 어려운 수식들을 도출하는 경향이 있다.
Worst-case 분석은 유사한 문제를 가진다: 일반적으로 정확한 worst-case 시나리오를 결정하는 게 불가능하다. 대신에, 최소 worst case 보다 나쁜 시나리오를 고려한다. 예를 들어, 알고리즘 분석시, 심지어 경로를 생성하는 정확한 입력을 결정하는 것이 불가능하더라도 (실재로 그러한 입력이 존재하지 않더라도), 가장 긴 가능한 경로를 찾는 것이 가능하다. (예를 들어 최대 루프 숫자를 고려하기) 이는 안전한 분석을 도출하나(worst case는 결코 과소평가 될 수 없다), 이 경로를 요구하는 입력이 없을 수 있기 때문에, 이는 비관적이다.
최악의 경우 분석 역시도 비슷한 문제점을 가진다. 일반적으로 최악의 경우 시나리오를 정밀하게 정의하는 것은 불가능하다. 대신에, 최악의 경우 못지않게 안 좋은 시나리오를 고려한다. 예를 들어 경로 생성 알고리즘 분석시, 경로를 생성하기 위한 정확한 입력을 결정하는 것이 불가능하더라도 (실제로 그러한 입력이 존재하지 않더라도) 가장 긴 가능한 경로를 찾는 것은 가능하다(예를 들어 최대 루프 횟수). 최악의 경우 분석은 과소추정(underestimate) 하지 않기 때문에 안정한 분석을 도출한다. 그러나 해당 경로를 요구하는 입력이 없을 수 있기 때문에 매우 비관적인 분석이 될 수 있다.
그 대신에 실제 최악의 경우와 매우 가깝다고 추정되는 시나리오를 고려 할 수 있다(그러나 더 나쁜 경우는 아니다). 이는 낙관적인 결과를 도출 할 수 있으며, 이 분석은 실제 최악의 경우를 과소추정 할 수 있다는 의미를 지닌다.
어떠한 상황에서는 안정성 보장을 위하여 비관적 분석이 필요할 수 있다. 그러나 비관적 분석은 자주 매우 비관적으로 변할 수 있으며, 낙관적으로 실제 값과 근접하게 분석하는 것이 훨씬 더 실질적인 접근법이 될 수 있다.
자주 짧은 수행시간이 걸리나 주기적으로 훨씬 긴 시간을 요구하는 알고리즘들을 분석 할 때, 분할상환분석(amortized analysis)은 연속적인 연산들의 최악의 경우 실행 시간을 결정하는데 활용될 수 있다.
이 분할상환 최악의 경우(amortized worst-case) 비용은 매우 평균 경우 비용(average case cost)와 근접함과 동시에 실행 시간의 상향치(upper limit)를 보장한다.
이 최악의 경우 분석은 최악의 경우 복잡도(worst-case complexity)와 연관된다.[2]
실제 결과들[편집]
최악의 경우 성능이 좋지 못한 많은 문제들은 좋은 평균 경우 성능을 가진다. 해결 하려는 문제들에 대하여 다음은 좋은 접근이다: 특정 사례(instance)들이 평균이기를 바란다. 암호술(cryptography)에서 다음은 매우 안 좋은 접근이다: 암호술 문제의 전형적인 사례들이 어려워지길 원한다. 최악의 경우가 평균 경우보다 더 어렵지 않거나, 또는 평균 경우가 최악의 경우 보다 더 쉽지 않은 것을 보이기 위하여, 랜덤 자가-감소성(random self-reducibility)과 같은 이 방법들이 활용될 수 있다.
반면에 최악의 경우 분석은 해시 테이블(hash table)과 같은 알고리즘에 매우 좋지 못한 결과를 얻는다. 그러나 충분한 크기의 잘 쓰인 해쉬 테이블은 통계적으로 절대 최악의 경우가 발생하지 않는다: 평균 연산 횟수는 기하급수적인 감소 곡선을 따르며, 연산의 실행 시간은 통계적으로 제한되기 때문이다.
예제[편집]
정렬 알고리즘[편집]
| 알고리즘 | 자료 구조 | 시간 복잡도:최선 | 시간 복잡도:평균 | 시간 복잡도:최악 | 공간 복잡도:최악 |
|---|---|---|---|---|---|
| 퀵 정렬 | 배열 | O(n log(n)) | O(n log(n)) | O(n2) | O(1) |
| 병합 정렬 | 배열 | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| 힙 정렬 | 배열 | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| 스무스 정렬 | 배열 | O(n) | O(n log(n)) | O(n log(n)) | O(1) |
| 버블 정렬 | 배열 | O(n2) | O(n2) | O(n2) | O(1) |
| 삽입 정렬 | 배열 | O(n) | O(n2) | O(n2) | O(1) |
| 선택 정렬 | 배열 | O(n2) | O(n2) | O(n2) | O(1) |
- 삽입 정렬 리스트에 n개의 모두 다른 원소가 있고 초기 랜덤 순서로 나열되어 있다고 가정하자. 평균적으로 리스트의 A1 ... Aj까지 절반의 원소들은 Aj+1 보다 작은 값을 가지고 절반은 큰 값을 가진다. 그러므로 알고리즘은 (j + 1)번째 원소와 평균적으로 절반의 이미 정렬된 서브-리스트(sub-list)가 비교하며tj = j/2 가 된다. 계산 결과 평균 경우 실행 시간은 최악의 경우 실행 시간과 비슷하게 입력 크기에 대한 이차 함수 형태이다.
- 퀵 정렬 위와 동일하게 리스트에 n개의 모두 다른 원소가 있고 초기 랜덤 순서로 나열되어 있다고 가정하자. 퀵 정렬은 평균 경우 성능이 O(n log(n))이며 실제로 이는 매우 빠른 정렬 알고리즘에 속한다. 그러나 최악의 경우 입력이 주어졌을 경우, 성능이 O(n2)까지 저하된다. 또한 “가장 짧은 것 먼저(shortest first)” 방법으로 구현되지 않았다면, 최악의 경우 공간 복잡도(worst-case space complexity)는 O(log(n))로 성능이 저하된다.
자료 구조[편집]
| 자료 구조 | 시간 복잡도:평균:인덱싱 | 시간 복잡도:평균:탐색 | 시간 복잡도:평균:삽입 | 시간 복잡도:평균:삭제 | 시간 복잡도:최악:인덱싱 | 시간 복잡도:최악:탐색 | 시간 복잡도:최악:삽입 | 시간 복잡도:최악:삭제 | 공간 복잡도:최악 |
|---|---|---|---|---|---|---|---|---|---|
| 기본 배열 | O(1) | O(n) | – | -– | O(1) | O(n) | – | – | O(n) |
| 동적 배열 | O(1) | O(n) | O(n) | – | O(1) | O(n) | O(n) | – | O(n) |
| 단일 연결 리스트 | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 이중 연결 리스트 | O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) |
| 해시 테이블 | - | O(1) | O(1) | O(1) | – | O(n) | O(n) | O(n) | O(n) |
| 이진 탐색 트리 | – | O((log n)) | O((log n)) | O((log n)) | – | O(n) | O(n) | O(n) | O(n) |
| B 트리 | – | O((log n)) | O((log n)) | O((log n)) | – | O((log n)) | O((log n)) | O((log n)) | O(n) |
| 레드-블랙 트리 | – | O((log n)) | O((log n)) | O((log n)) | – | O((log n)) | O((log n)) | O((log n)) | O(n) |
| AVL 트리 | – | O((log n)) | O((log n)) | O((log n)) | – | O((log n)) | O((log n)) | O((log n)) | O(n) |
- 선형 검색 리스트에 n개의 원소가 있다고 가정하자. 완전히 최악의 경우(absolute worst case)에 선형 검색은 모든 원소들을 한 번씩 방문해야 한다. 이 경우는 찾고자 하는 원소가 리스트의 마지막에 위치하거나 없는 경우 발생한다. 그러나 찾고자 하는 원소가 리스트에 있고 균등하게 분배되었다고 하면 평균적으로 선형 검색은 n/2 원소를 방문 할 것이다.
같이 보기[편집]
각주[편집]
- ↑ Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".
- ↑ “Worst-case complexity” (PDF). 2011년 7월 21일에 원본 문서 (PDF)에서 보존된 문서. 2017년 1월 4일에 확인함.