베스트, 워스트, 평균 케이스
Best, worst and average case |
컴퓨터 과학에서 주어진 알고리즘의 베스트 케이스, 워스트 케이스 및 평균 케이스는 각각 최소 자원 사용량, 최대 자원 사용량, 평균 자원 사용량을 나타냅니다.일반적으로 고려되는 리소스는 실행 시간(즉, 시간의 복잡성)이지만 메모리 또는 다른 리소스일 수도 있습니다.최적의 경우는 n개의 요소의 입력 데이터에 대해 최소한의 스텝 수를 수행하는 기능이다.최악의 경우는 n 사이즈의 입력 데이터에 대해 최대 스텝 수를 실행하는 기능입니다.Average case는 n개 요소의 입력 데이터에 대해 평균 스텝 수를 수행하는 함수이다.
실시간 컴퓨팅에서는 알고리즘이 항상 제시간에 완료되도록 하기 위해 최악의 경우 어느 정도의 시간이 필요한지 아는 것이 중요하기 때문에 최악의 경우 실행 시간이 특히 중요합니다.
알고리즘 분석에서는 평균 퍼포먼스와 최악의 퍼포먼스가 가장 많이 사용됩니다.베스트 케이스의 퍼포먼스는 그다지 널리 알려져 있지 않지만, 예를 들어 개별 태스크의 베스트 케이스가 알려져 있는 경우, 그것들을 사용하여 전체적인 최악의 케이스 분석의 정확성을 향상시킬 수 있습니다.컴퓨터 과학자는 확률론적 분석 기법, 특히 기대치를 사용하여 예상 실행 시간을 결정합니다.
이 용어는 다른 맥락에서 사용됩니다. 예를 들어 전염병의 최악의 경우 및 최상의 경우, 전자 회로 소자가 노출되는 최악의 경우 온도 등입니다.지정된 공차의 컴포넌트가 사용되는 경우 장치는 공차와 외부 조건의 최악의 조합으로 올바르게 작동하도록 설계되어야 합니다.
알고리즘에 최적인 퍼포먼스
최적의 성능이라는 용어는 컴퓨터 과학에서 최적의 조건에서 알고리즘의 동작을 설명하기 위해 사용됩니다.예를 들어, 목록에서 단순 선형 검색의 가장 좋은 경우는 원하는 요소가 목록의 첫 번째 요소일 때 발생합니다.
알고리즘의 개발이나 선택은 베스트 케이스의 퍼포먼스에 근거하는 경우는 거의 없습니다.대부분의 학계 및 상업계 기업은 평균 케이스의 복잡성과 최악의 케이스의 퍼포먼스 향상에 더 관심이 있습니다.알고리즘은 한정된 입력 세트에 대한 솔루션을 하드 코딩함으로써 최적의 실행 시간을 갖도록 수정될 수 있으며, 이 측정이 거의 [1]무의미해집니다.
최악의 경우와 상각 후의 경우와 평균 경우의 퍼포먼스
| 이 섹션은 어떠한 출처도 인용하지 않습니다.(2017년 9월 (이 및 ) |
최악의 경우 성능 분석과 평균적인 경우 성능 분석에는 몇 가지 유사점이 있지만, 실제로는 다른 도구와 접근 방식이 필요합니다.
일반적인 입력 수단을 결정하는 것은 어렵고, 그 평균적인 입력은 수학적으로 특징짓기 어려운 속성을 가지고 있는 경우가 많습니다(예를 들어 텍스트 문자열로 동작하도록 설계된 알고리즘).마찬가지로, 특정 "평균 사례"에 대한 합리적인 설명이 가능하더라도(아마도 알고리즘의 일부 사용에만 적용될 수 있음), 그들은 [2]방정식의 더 어려운 분석을 초래하는 경향이 있다.
최악의 경우 분석은 안전한 분석(최악의 경우는 과소평가되지 않음)을 제공하지만, 이렇게 많은 단계를 거치는 (현실적인) 입력이 없을 수 있기 때문에 지나치게 비관적일 수 있습니다.
경우에 따라서는 안전을 보장하기 위해 비관적인 분석을 사용해야 할 수도 있다.그러나 비관적인 분석은 종종 너무 비관적일 수 있으므로 실제 값에 가깝지만 낙관적일 수 있는 분석(아마도 고장 확률이 낮은 것으로 알려진 분석)이 훨씬 더 실용적인 방법이 될 수 있습니다.최악의 경우 분석과 평균적인 경우 분석 사이의 갭을 메우기 위한 학술 이론의 한 가지 현대적인 접근법은 평활 분석이라고 불립니다.
완료하는 데 짧은 시간이 걸리지만 정기적으로 훨씬 더 긴 시간이 필요한 알고리즘을 분석할 때 상각된 분석을 사용하여 일련의 작업에 걸쳐 최악의 경우 실행 시간을 결정할 수 있습니다.이 상각된 비용은 평균 비용에 훨씬 가까울 수 있지만, 실행 시간의 상한은 보장됩니다.따라서 온라인 알고리즘은 상각된 분석을 기반으로 하는 경우가 많습니다.
최악의 경우 분석은 최악의 경우 [3]복잡성과 관련이 있습니다.
실제 결과
최악의 경우 성능이 나쁜 알고리즘의 대부분은 평균적인 경우 성능이 우수합니다.해결하고 싶은 문제에 대해서는, 이것은 좋은 일입니다.즉, 우리가 관심을 가지는 특정의 인스턴스가 평균이길 바랄 수 있습니다.암호화의 경우 이는 매우 좋지 않습니다.암호화 문제의 일반적인 인스턴스를 어렵게 만들고 싶습니다.여기서 랜덤 자기축소성 등의 방법을 사용하여 특정 문제에 대해 최악의 경우가 평균적인 경우보다 어렵지 않음을 나타내거나 평균적인 경우가 최악의 경우보다 쉽지 않음을 나타낼 수 있습니다.
한편 해시 테이블과 같은 일부 데이터 구조에는 최악의 경우 동작이 매우 불량하지만 충분한 크기의 해시 테이블은 통계적으로 최악의 경우를 나타내지 않습니다.실행되는 평균 연산 수는 지수 붕괴 곡선을 따르기 때문에 동작의 실행 시간은 통계적으로 한정됩니다.
예
정렬 알고리즘
| 알고리즘. | data 구조 | 시간의 복잡성:최량 | 시간의 복잡성:평균 | 시간의 복잡성:최악의 | 공간의 복잡성:최악의 |
|---|---|---|---|---|---|
| 빠른 정렬 | 어레이 | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| 병합 정렬 | 어레이 | 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(n) | O(n2) | O(n2) | O(1) |
| 삽입 정렬 | 어레이 | O(n) | O(n2) | O(n2) | O(1) |
| 선택 정렬 | 어레이 | O(n2) | O(n2) | O(n2) | O(1) |
| 보고 정렬 | 어레이 | O(n) | O(nn!) | O()) | O(1) |
- n개의 요소 목록에 적용되는 삽입 정렬로, 모두 다른 것으로 간주되며 처음에는 랜덤 순서로 정렬됩니다.평균적으로1 목록 A에 있는 요소의 절반이...A는 요소j+1 A보다 작고 절반은 더 큽니다j.따라서 알고리즘은 평균적으로 삽입할 (j + th1) 요소를 이미 정렬된 하위 목록의 절반과 비교하므로j t = j/2입니다.결과 평균 실행 시간을 계산하면 최악의 실행 시간과 마찬가지로 입력 크기의 2차 함수를 얻을 수 있습니다.
- n개의 요소 목록에 적용된 QuickSort는 모두 다른 것으로 간주되며 처음에는 랜덤 순서입니다.이 일반적인 정렬 알고리즘은 평균 O(n log(n)의 성능을 가지며, 실제로 매우 빠른 알고리즘이 됩니다.그러나 최악의 경우 입력은 O(n2)로 성능이 저하됩니다.또, 「최단 우선」정책으로 실장했을 경우, 대신에 최악의 스페이스 복잡도는 O(log(n)로 한정됩니다.
- 힙소트에는 모든 요소가 동일한 O(n) 시간이 있습니다.Heapify에는 O(n) 시간이 걸리고 각 n개 요소에 대해 O(1) 시간이 걸립니다.모든 요소가 고유해야 할 경우 실행 시간이 O(nlog(n)로 증가합니다.
- 첫 번째 반복에서 요소가 정렬될 때 보고소트에는 O(n) 시간이 있습니다.각 반복에서 모든 요소가 순서대로 체크됩니다.n!개의 가능한 순열이 있습니다. 균형 난수 생성기를 사용하면 배열의 거의 모든 순열이 n!번복으로 산출됩니다.컴퓨터에는 메모리가 한정되어 있기 때문에 생성된 번호가 순환합니다.각 치환에 도달하지 못할 수 있습니다.최악의 경우 O()) 시간, 즉 무한 루프가 발생합니다.
데이터 구조
| data 구조 | 시간의 복잡성 | 공간의 복잡성 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 평균: 인덱싱 | 평균: 검색 | 평균: 삽입 | 평균: 삭제 | 최악: 인덱싱 | 최악: 검색 | 최악: 삽입 | 최악: 삭제 | 최악의 | |
| 기본 어레이 | O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | 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(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(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) | O(n) | O(n) | O(n) | O(nlog(n)) |
| 해시 테이블 | — | O(1) | O(1) | O(1) | — | O(n) | O(n) | O(n) | O(n) |
| 이진 검색 트리 | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
| 데카르트 나무 | — | O(로그(n)) | O(로그(n)) | O(로그(n)) | — | O(n) | O(n) | O(n) | O(n) |
| B-트리 | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) |
| 붉은색-검은색 | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) |
| 스플레이 트리 | — | O(로그(n)) | O(로그(n)) | O(로그(n)) | — | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) |
| AVL 트리 | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) |
| K-D 트리 | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(로그(n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
- n개의 요소 목록에 대한 선형 검색.최악의 경우 검색은 모든 요소를 한 번 방문해야 합니다.이 문제는 검색되는 값이 목록의 마지막 요소이거나 목록에 없는 경우에 발생합니다.그러나 평균적으로 검색된 값이 목록에 있고 각 목록 요소가 검색된 값일 가능성이 같다고 가정하면 검색은 n/2 요소만 방문합니다.
「 」를 참조해 주세요.
- 정렬 알고리즘– 다양한 알고리즘의 퍼포먼스 분석이 많은 영역입니다.
- 검색 데이터 구조 – 특정 항목을 효율적으로 검색할 수 있는 데이터 구조
- 최악의 경우 회로 분석
- 평활 분석
- 구간 유한 요소
- 빅 O 표기법
레퍼런스
- ^ 알고리즘 소개(Cormen, Leiserson, Rivest 및 Stein) 2001, 2장 "시작"Best-case complexity에서는 입력 인스턴스의 알고리즘 실행 시간 하한을 지정합니다.
- ^ Spielman, Daniel; Teng, Shang-Hua (2009), "Smoothed analysis: an attempt to explain the behavior of algorithms in practice" (PDF), Communications of the ACM, ACM, 52 (10): 76-84, doi:10.1145/1562764.1562785, S2CID 7904807
- ^ "Worst-case complexity" (PDF). Archived (PDF) from the original on 2011-07-21. Retrieved 2008-11-30.
