최선, 최악, 그리고 평균의 경우
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
알고리즘의 성능은 최선의 경우, 평균의 경우, 최악의 경우로 분석하며, 평균 경우 성능은 알고리즘 선택의 중요한 지표가 된다. 최악의 경우 분석은 분할상환분석과 연관되며, 안전성 보장을 위해 비관적 분석이 필요할 수 있지만 지나치게 비관적일 수 있다. 다양한 정렬 알고리즘(퀵 정렬, 병합 정렬, 힙 정렬, 삽입 정렬 등)과 자료 구조(배열, 연결 리스트, 해시 테이블, 이진 탐색 트리 등)는 각기 다른 시간 및 공간 복잡도를 가지며, 특정 상황에 맞는 선택이 중요하다.
더 읽어볼만한 페이지
| 최선, 최악, 그리고 평균의 경우 |
|---|
2. 알고리즘 성능 분석
알고리즘의 성능을 평가하고 비교하는 것은 전산학에서 중요한 과제이다. 알고리즘의 실행 시간이나 자원 사용량은 입력 데이터에 따라 달라질 수 있으므로, 다양한 상황을 고려한 분석이 필요하다. 일반적으로 알고리즘 성능은 다음과 같은 경우로 나누어 분석한다.
- 최선의 경우(best-case performanceeng): 알고리즘이 가장 유리한, 최적의 조건에서 동작할 때의 성능이다. 실제 알고리즘 선택이나 개발에서는 주요 고려 대상이 아닌 경우가 많다.[4]
- 평균의 경우(average-case performanceeng): '평균적인' 입력에 대한 알고리즘의 기대 성능이다. 현실적인 성능 예측에 도움이 될 수 있으나, '평균적인' 입력을 정의하고 분석하는 것이 어려울 수 있다.[2]
- 최악의 경우(worst-case performanceeng): 알고리즘이 가장 불리한 조건에서 동작할 때의 성능이다. 성능의 상한선을 보장하여 안정성이 중요한 경우 유용하지만, 분석 결과가 지나치게 비관적일 수 있다.[2][3][5]
이 세 가지 분석 방법은 서로 유사점도 있지만, 분석을 위한 도구나 접근 방식에는 차이가 있다.[2] 때로는 평소에는 빠르지만 간헐적으로 매우 느린 연산이 포함된 알고리즘의 성능을 더 정확하게 평가하기 위해 분할상환 분석(amortized analysis)과 같은 기법이 사용되기도 한다. 이는 연속된 연산들에 대한 평균적인 최악 성능을 평가하여, 평균 비용과 유사하면서도 실행 시간의 상한을 보장하는 장점이 있다. 또한, 최악 경우와 평균 경우 분석 사이의 간극을 줄이기 위한 시도로 평활 분석(smoothed analysis)과 같은 방법도 연구되고 있다.
2. 1. 최선의 경우
"최선의 경우 성능"(best-case performanceeng)은 전산학에서 알고리즘이 가장 이상적인, 즉 최적의 조건에서 어떻게 동작하는지를 설명하는 데 사용되는 용어이다. 예를 들어, 리스트(list)에서 특정 원소를 찾는 간단한 선형 검색 알고리즘을 생각해 볼 때, 찾고자 하는 원소가 리스트의 가장 처음에 위치하는 경우가 바로 최선의 경우에 해당한다.알고리즘을 개발하거나 선택하는 과정에서 최선의 경우 성능을 중요한 기준으로 삼는 경우는 거의 없다. 대부분의 학술 연구나 실제 산업 현장에서는 알고리즘의 평균-경우 복잡도나 최악의 경우 성능을 개선하는 데 더 많은 노력을 기울인다.[4][1] 또한, 특정 몇몇 입력 값에 대해서만 빠르게 동작하도록 미리 답을 정해놓는 방식(하드 코딩, hard-coding)으로 알고리즘을 수정하면 최선의 경우 실행 시간을 인위적으로 좋게 만들 수 있지만, 이러한 접근은 실질적인 의미가 거의 없다.[1]
2. 2. 평균의 경우
최악 경우 성능 분석과 평균 경우 성능 분석은 몇 가지 유사점을 가지고 있지만, 실제 분석을 위해서는 일반적으로 다른 도구와 접근 방식이 필요하다.알고리즘의 평균 경우 성능을 분석하기 위해서는 먼저 '평균적인 입력'이 무엇인지 정의해야 하는데, 이것은 상당히 어려운 문제이다. 평균적인 입력은 종종 수학적으로 명확하게 표현하기 어려운 특징을 가지기 때문이다. 예를 들어, 문자열을 처리하는 알고리즘의 평균적인 입력 문자열이 무엇인지 정의하기는 쉽지 않다.[2] 설령 특정 상황에서의 "평균 경우"를 합리적으로 정의할 수 있다 하더라도, 이를 분석하는 과정에서 매우 복잡한 수학적 계산이 필요한 경우가 많다.[2]
평균 경우 분석은 때때로 최악의 경우 분석보다 현실적인 성능을 예측하는 데 도움이 될 수 있다. 하지만 최악의 경우 분석은 알고리즘 성능의 상한선을 보장하여 안정성이 중요한 경우에 유용하다.
자주 짧은 시간이 걸리지만 주기적으로 훨씬 긴 시간이 필요한 알고리즘의 경우, 상각 분석(amortized analysis)이라는 기법을 사용하여 연속적인 연산에 대한 최악의 실행 시간을 분석할 수 있다. 이 '''상각된''' 최악 경우 비용은 평균 경우 비용과 상당히 비슷하면서도, 실행 시간에 대한 확실한 상한을 제공한다는 장점이 있다. 많은 온라인 알고리즘이 이러한 상각 분석을 기반으로 설계된다.
또한, 최악의 경우 분석과 평균 경우 분석 사이의 간극을 메우기 위한 시도로 평활 분석(smoothed analysis)과 같은 접근법도 연구되고 있다.
2. 3. 최악의 경우
최악의 경우(worst-case) 성능은 알고리즘이 가장 안 좋은 조건에서 실행될 때의 성능을 의미한다. 예를 들어, 정렬 알고리즘에서 데이터가 역순으로 정렬된 배열이 입력으로 주어지는 경우가 대표적인 최악의 경우에 해당한다. 최악의 경우 성능은 알고리즘의 안정성을 보장하는 중요한 지표이며, 특히 실시간 시스템과 같이 성능 예측이 중요한 분야에서 중요하게 고려된다.최악의 경우 성능 분석은 평균 경우 성능 분석과 유사성을 가지지만, 분석을 위해서는 다른 도구와 접근법이 요구된다.[2] 평균 경우 분석은 '평균 입력'을 정의하기 어렵다는 문제가 있다. 예를 들어 문자열 연산을 위한 알고리즘에서 평균적인 입력을 정의하기는 쉽지 않다.[2]
최악의 경우 분석 역시 정확한 최악의 시나리오를 결정하는 것이 일반적으로 불가능하다는 어려움이 있다. 대신, 분석 시에는 실제 최악의 경우보다 더 나쁘거나 최소한 그만큼 나쁜 시나리오를 가정하는 경우가 많다. 예를 들어, 알고리즘의 가능한 실행 경로 중 가장 긴 경로를 찾는 방식(예: 최대 루프 반복 횟수 고려)으로 분석할 수 있는데, 실제로 해당 경로를 실행시키는 입력이 존재하지 않을 수도 있다. 이러한 분석 방식은 최악의 경우를 과소평가하지 않기 때문에 안전한 분석 결과를 제공하지만, 실제 발생 가능성이 낮은 비현실적인 상황까지 고려하므로 지나치게 비관적인 분석이 될 수 있다.
상황에 따라서는 안전성 보장을 위해 이러한 비관적 분석이 필요할 수 있다. 하지만 지나치게 비관적인 분석 결과는 실용성이 떨어질 수 있으므로, 실제 최악의 경우와 가깝다고 추정되는 시나리오(하지만 더 나쁘지는 않은)를 고려하는 덜 비관적인 분석이 더 실질적인 접근법이 될 수도 있다. 다만 이 경우 실제 최악의 경우를 과소평가할 위험(낙관적인 결과)이 있다. 최악의 경우 분석과 평균 경우 분석 사이의 간극을 해소하려는 시도로 평활 분석(smoothed analysis)이라는 방법도 연구되고 있다.
또한, 평소에는 실행 시간이 짧지만 주기적으로 훨씬 긴 시간이 소요되는 알고리즘의 경우, 분할상환 분석(amortized analysis)을 사용하여 연속된 연산들의 최악 실행 시간을 결정할 수 있다. 이 분할상환 최악 비용(amortized worst-case cost)은 평균 비용(average case cost)과 매우 근접하면서도 실행 시간의 상한치(upper limit)를 보장한다. 온라인 알고리즘 등이 분할상환 분석에 기반하는 경우가 많다.
최악의 경우 분석은 최악의 경우 복잡도와 밀접하게 연관된다.[3][5] 최악의 경우 성능이 좋지 않은 많은 문제나 알고리즘도 실제로는 좋은 평균 성능을 보이는 경우가 많다. 예를 들어 해시 테이블은 이론적으로 최악의 경우 성능이 매우 나쁠 수 있지만, 실제 잘 구현된 해시 테이블에서는 통계적으로 최악의 경우가 거의 발생하지 않는다. 반면, 암호학 분야에서는 일반적인 경우가 어려운 것이 중요하므로, 최악의 경우가 평균적인 경우보다 어렵지 않거나 그 반대임을 보이기 위해 무작위 자기 축약성(random self-reducibility)과 같은 방법을 사용하기도 한다.
2. 4. 분할 상환 분석
알고리즘 분석에서, 어떤 연산은 대부분 짧은 시간이 걸리지만 때때로 훨씬 긴 시간이 소요될 수 있다. 이러한 알고리즘들을 분석할 때, 연속적인 연산들의 최악의 경우 실행 시간을 결정하기 위해 분할상환 분석(amortized analysis) 기법을 활용할 수 있다.분할 상환 분석을 통해 얻는 최악의 경우 비용, 즉 '''분할 상환 비용'''(amortized cost)은 실제 평균 비용과 매우 가까우면서도, 전체 연산 시간에 대한 상한선을 보장한다는 장점이 있다. 이는 일부 연산이 비정상적으로 오래 걸리더라도, 전체 연산 과정을 놓고 보면 평균적인 비용은 낮게 유지될 수 있음을 의미한다.
이러한 특징 때문에 분할 상환 분석은 특히 온라인 알고리즘과 같이 연속적인 입력에 따라 실시간으로 작동해야 하는 알고리즘을 분석하는 데 유용하게 활용된다.
분할 상환 분석은 최악의 경우 복잡도와 관련이 있다.[3]
3. 정렬 알고리즘의 성능 비교
정렬 알고리즘의 성능은 주로 시간 복잡도와 공간 복잡도를 기준으로 평가된다. 시간 복잡도는 입력 데이터의 크기(''n'')에 따라 알고리즘 실행 시간이 어떻게 증가하는지를 나타내며, 공간 복잡도는 알고리즘 실행에 필요한 추가 메모리 공간의 양을 의미한다.
특히 정렬 알고리즘의 성능을 비교할 때는 최선(best), 평균(average), 최악(worst)의 세 가지 경우를 모두 고려하는 것이 중요하다. 어떤 알고리즘은 평균적으로 매우 효율적이지만 특정 입력 데이터(최악의 경우)에 대해서는 성능이 급격히 저하될 수 있다. 예를 들어, 퀵 정렬은 평균적으로 O(''n'' log(''n''))의 빠른 성능을 보이지만, 이미 정렬된 데이터 등이 입력될 경우 최악에는 O(''n''2)까지 성능이 떨어질 수 있다. 반면 병합 정렬은 최선, 평균, 최악 모두 O(''n'' log(''n''))의 일정한 시간 복잡도를 가지지만, O(''n'')의 추가 공간을 필요로 하는 단점이 있다. 힙 정렬은 O(''n'' log(''n''))의 시간 복잡도와 O(1)의 공간 복잡도를 가져 효율적이지만, 실제 실행 속도 면에서는 퀵 정렬보다 느릴 수 있다. 삽입 정렬과 같이 간단한 알고리즘은 최선의 경우 O(''n'')으로 매우 빠르지만, 평균 및 최악의 경우 O(''n''2)으로 비효율적일 수 있다.
따라서 특정 상황에 가장 적합한 정렬 알고리즘을 선택하기 위해서는 이러한 다양한 측면을 종합적으로 비교하고 분석해야 한다. 각 알고리즘의 구체적인 성능 특성은 하위 섹션에서 자세히 다룬다.
3. 1. 퀵 정렬
퀵 정렬은 리스트에 ''n''개의 모두 다른 원소가 있고 초기 랜덤 순서로 나열되어 있다고 가정할 때, 평균적인 경우 O(''n'' log(''n''))의 시간 복잡도를 가진다. 이 덕분에 퀵 정렬은 실제로 매우 빠른 정렬 알고리즘 중 하나로 평가받는다.그러나 입력 값의 특성에 따라 최악의 경우에는 성능이 O(''n''2)까지 저하될 수 있다는 단점도 가지고 있다. 공간 복잡도는 구현 방식에 따라 달라질 수 있다. 예를 들어 “가장 짧은 것 먼저(shortest first)” 방식으로 구현하면 최악의 경우에도 공간 복잡도를 O(log(''n'')) 수준으로 유지할 수 있다. 하지만 일반적인 최악의 경우 공간 복잡도는 O(''n'')이 될 수 있다.
3. 2. 병합 정렬
병합 정렬은 정렬 알고리즘의 하나로, 입력 데이터가 어떻게 정렬되어 있든 관계없이 항상 일정한 성능을 보인다. 최선의 경우, 평균적인 경우, 그리고 최악의 경우 모두에서 시간 복잡도는 O(''n'' log ''n'')이다. 이는 데이터의 양이 많아져도 비교적 효율적으로 정렬할 수 있음을 의미한다.그러나 병합 정렬은 정렬 과정에서 원본 데이터 크기만큼의 추가적인 메모리 공간을 필요로 한다는 단점이 있다. 따라서 공간 복잡도는 O(''n'')이다.
병합 정렬은 안정 정렬(stable sort)의 특성을 가지고 있다. 이는 정렬 과정에서 값이 동일한 원소들이 있을 경우, 이들의 상대적인 순서가 정렬 전과 동일하게 유지된다는 것을 의미한다.
3. 3. 힙 정렬
힙 정렬은 배열 자료 구조를 기반으로 동작하며, 최선, 평균, 최악의 경우 모두 O(''n'' log(''n''))의 시간 복잡도를 나타낸다. 이는 입력 데이터의 초기 상태와 관계없이 일정한 성능을 보장하는 장점이다. 또한, 정렬 과정에서 추가적인 메모리 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)로 매우 효율적이다.다만, 정렬하려는 모든 요소가 동일한 값을 가지는 특수한 경우에는 힙을 구성하는 과정(힙화)에 O(''n'') 시간이 소요되고, 이후 각 요소를 힙에서 제거하는 데 O(1) 시간이 걸리므로 전체 시간 복잡도는 O(''n'')이 될 수 있다. 그러나 일반적으로 요소들이 서로 다른 값을 가지는 경우에는 O(''n'' log(''n''))의 시간 복잡도를 가진다.
3. 4. 삽입 정렬
삽입 정렬은 배열 자료 구조를 사용하여 구현될 수 있다. 시간 복잡도를 살펴보면, 최선의 경우 O(''n'')의 성능을 보인다. 이는 입력 배열이 이미 정렬되어 있거나 거의 정렬된 상태일 때 매우 효율적으로 동작할 수 있음을 의미한다.그러나 평균적인 경우와 최악의 경우 모두 시간 복잡도는 O(''n''2)이다. 평균적인 경우를 분석해보면, 리스트에 ''n''개의 서로 다른 원소가 무작위 순서로 나열되어 있다고 가정할 때, (''j'' + 1)번째 원소를 올바른 위치에 삽입하기 위해 평균적으로 이미 정렬된 앞부분(''A''1 ... ''A''''j'') 리스트 요소들의 절반과 비교하게 된다(''t''''j'' = ''j''/2). 결과적으로 평균 실행 시간은 최악의 경우와 마찬가지로 입력 크기 ''n''에 대한 이차 함수 형태를 가지게 된다.
공간 복잡도의 경우, 최악의 경우에도 O(1)으로, 정렬 과정에서 추가적인 메모리 공간을 거의 필요로 하지 않는다.
3. 5. 기타 정렬 알고리즘
버블 정렬이나 선택 정렬과 같은 일부 정렬 알고리즘은 구현이 비교적 간단하지만, 평균 및 최악의 경우 시간 복잡도가 O(''n''2)로 나타나 일반적으로 효율성이 떨어진다.- 삽입 정렬: 리스트에 ''n''개의 서로 다른 원소가 무작위 순서로 나열되어 있다고 가정할 때, 평균적으로 (''j'' + 1)번째 원소를 삽입하기 위해 이미 정렬된 앞부분 리스트(''A''1 ... ''A''''j'')의 절반 정도와 비교하게 된다. 이 때문에 평균 실행 시간은 최악의 경우와 마찬가지로 입력 크기 ''n''에 대해 O(''n''2)의 이차 함수 형태를 보인다. 다만, 이미 정렬된 리스트가 입력될 경우 최선의 시간 복잡도는 O(''n'')이다.
- 퀵 정렬: 퀵 정렬은 널리 사용되는 정렬 알고리즘으로, 평균적으로 O(''n'' log(''n''))의 우수한 성능을 보여 매우 빠른 알고리즘 중 하나이다. 그러나 입력 데이터의 배열 상태에 따라 최악의 경우에는 성능이 O(''n''2)까지 저하될 수 있다. 또한 "최단 우선" (shortest first) 정책으로 구현하지 않으면 최악의 경우 공간 복잡도는 O(''n'')이 될 수 있으나, 해당 정책을 사용하면 O(log(''n''))으로 제한될 수 있다.
- 힙 정렬: 모든 요소가 동일한 값일 경우 O(''n'')의 시간 복잡도를 가진다. 이는 힙 구성(heapify)에 O(''n'') 시간이 걸리고, 각 요소를 힙에서 제거하는 데 O(1) 시간이 소요되기 때문이다. 요소들이 모두 다른 고유한 값일 경우에는 O(''n'' log(''n''))의 시간 복잡도를 보인다. 힙 정렬의 장점 중 하나는 추가 공간 복잡도가 O(1)이라는 점이다.
- 보고 정렬 (Bogo sort): 보고 정렬은 매우 비효율적인 알고리즘이다. 최선의 경우, 즉 첫 번째 시도에서 요소가 정렬된 순서로 나타나면 O(''n'')의 시간이 걸린다. 각 반복에서 모든 요소가 순서대로인지 확인하며, 무작위로 섞는 과정을 반복한다. 가능한 순열은 ''n''!가지이므로, 평균적으로는 O(''n'' ''n''!)의 시간 복잡도를 가진다. 균형 잡힌 난수 생성기를 사용하더라도, 실제 컴퓨터의 메모리 제한으로 인해 생성되는 난수 순열이 순환될 수 있어 모든 순열에 도달하지 못할 수도 있다. 최악의 경우에는 정렬된 순서를 영원히 찾지 못하고 무한 루프(O(∞))에 빠질 수 있다.
다음은 여러 정렬 알고리즘의 시간 및 공간 복잡도를 비교한 표이다.
| 알고리즘 | 자료구조 | 시간 복잡도: 최선 | 시간 복잡도: 평균 | 시간 복잡도: 최악 | 공간 복잡도: 최악 |
|---|---|---|---|---|---|
| 퀵 정렬 | 배열 | 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(n n!) | O(∞) | O(1) |
4. 자료 구조의 성능 비교
다양한 자료 구조는 특정 연산을 수행하는 데 있어 각기 다른 성능 특성을 보인다. 특히 데이터의 탐색, 삽입, 삭제와 같은 기본 연산에 대한 시간 복잡도는 자료 구조를 선택하는 중요한 기준이 된다. 시간 복잡도는 평균적인 경우와 최악의 경우로 나누어 평가하며, 이는 데이터의 분포나 특정 상황에 따라 성능이 어떻게 달라질 수 있는지를 보여준다.
아래 표는 주요 자료 구조들의 연산별 평균 및 최악 시간 복잡도와 공간 복잡도를 비교하여 보여준다.
| 자료 구조 | 시간 복잡도 | 공간 복잡도 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 평균: 인덱싱 | 평균: 탐색 | 평균: 삽입 | 평균: 삭제 | 최악: 인덱싱 | 최악: 탐색 | 최악: 삽입 | 최악: 삭제 | 최악 | |
| 기본 배열 | 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(log (n)) | O(log (n)) | O(log (n)) | O(log (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(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | 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(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(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(log (n)) | O(log (n)) | O(n) |
| K-d 트리 | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
표에서 볼 수 있듯이, 배열은 인덱스를 통한 접근이 매우 빠르지만(O(1)), 탐색, 삽입, 삭제는 상대적으로 느릴 수 있다(O(''n'')). 반면 연결 리스트는 삽입과 삭제가 빠르지만(O(1)), 탐색과 인덱싱은 느리다(O(''n'')). 해시 테이블은 평균적으로 매우 빠른 성능(O(1))을 보이지만, 최악의 경우 성능이 크게 저하될 수 있다(O(''n'')). 이진 탐색 트리와 그 변형들(B-트리, 레드-블랙 트리, AVL 트리 등)은 평균 및 최악의 경우 모두 비교적 안정적인 로그 시간(O(log ''n'')) 성능을 제공하는 경우가 많다.
각 자료 구조의 구체적인 특징과 성능 분석은 해당 자료 구조를 다루는 하위 섹션에서 더 자세히 설명한다.
4. 1. 배열
배열은 데이터를 저장하고 처리하는 데 가장 기본적으로 사용되는 자료 구조 중 하나이다. 배열의 가장 큰 장점은 인덱스를 이용하여 특정 위치의 원소에 빠르게 접근할 수 있다는 점이다. 이는 시간 복잡도로 O(1)에 해당한다.하지만 배열에서 특정 값을 탐색하거나, 중간에 원소를 삽입 또는 삭제하는 연산은 평균적으로나 최악의 경우 모두 O(''n'')의 시간이 소요될 수 있다. 이는 배열의 모든 원소를 순차적으로 확인하거나, 삽입/삭제 후 원소들을 이동시켜야 할 수 있기 때문이다.
배열에는 크기가 고정된 기본 배열과 크기가 동적으로 변할 수 있는 동적 배열이 있다. 각 배열 유형의 연산별 시간 복잡도와 공간 복잡도는 다음과 같다.
| 자료 구조 | 시간 복잡도 | 공간 복잡도 (최악) | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 평균: 인덱싱 | 평균: 탐색 | 평균: 삽입 | 평균: 삭제 | 최악: 인덱싱 | 최악: 탐색 | 최악: 삽입 | 최악: 삭제 | ||
| 기본 배열 | 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(1)로 매우 효율적이지만, 탐색, 삽입은 O(''n'')의 시간 복잡도를 가진다. 기본 배열의 경우 삭제도 O(''n'')이지만, 동적 배열의 삭제 시간 복잡도는 연산 방식에 따라 달라질 수 있어 위 표에서는 명시적으로 표기되지 않았다. 공간 복잡도는 두 경우 모두 저장하는 원소의 수에 비례하여 O(''n'')이다.
4. 2. 연결 리스트
연결 리스트는 필요에 따라 크기를 동적으로 조절할 수 있는 자료 구조이다.단일 연결 리스트와 이중 연결 리스트 모두 평균 및 최악의 경우에서 삽입과 삭제 연산은 O(1)의 시간 복잡도를 가진다. 이는 특정 노드를 이미 알고 있을 때 해당 노드의 앞이나 뒤에 새로운 노드를 추가하거나 기존 노드를 제거하는 작업이 리스트의 전체 크기와 무관하게 상수 시간에 완료될 수 있음을 의미한다.
반면, 특정 값을 찾거나 특정 위치(인덱스)의 원소에 접근하는 탐색 및 인덱싱 연산은 평균 및 최악의 경우 모두 O(''n'')의 시간 복잡도를 가진다. 이는 원하는 원소를 찾기 위해 리스트의 처음부터 순차적으로 확인해야 할 수 있기 때문이다. 최악의 경우, 찾고자 하는 원소가 리스트의 마지막에 있거나 존재하지 않으면 리스트의 모든 원소(''n''개)를 방문해야 한다. 평균적으로는 약 ''n''/2개의 원소를 방문하게 된다.
공간 복잡도는 저장하는 원소의 수(''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) |
4. 3. 해시 테이블
해시 테이블은 자료 구조의 한 종류로, 특정 연산에서 평균적으로 매우 효율적인 성능을 보여준다. 원본 자료에 제시된 표에 따르면, 해시 테이블의 평균 시간 복잡도는 탐색, 삽입, 삭제 연산 모두에서 O(1)이다. 이는 데이터의 크기와 관계없이 연산 속도가 평균적으로 일정하게 유지된다는 것을 의미한다.그러나 최악의 경우에는 성능이 크게 저하될 수 있다. 해시 테이블의 최악 시간 복잡도는 탐색, 삽입, 삭제 연산 모두 O(''n'')이다. 이는 해시 함수의 충돌이 많이 발생하여 저장된 데이터들이 한 곳에 집중될 경우, 마치 연결 리스트를 순차적으로 탐색하는 것과 유사한 상황이 발생하기 때문이다.
공간 복잡도의 경우, 해시 테이블은 최악의 경우 O(''n'')의 공간을 필요로 한다. 이는 저장해야 할 데이터의 개수(''n'')에 비례하여 메모리 사용량이 증가한다는 것을 뜻한다.
결론적으로 해시 테이블은 평균적으로 매우 빠른 성능을 제공하지만, 해시 충돌과 같은 특정 상황에서는 성능이 선형적으로 감소할 수 있는 특징을 지닌 자료 구조이다.
4. 4. 이진 탐색 트리
이진 탐색 트리는 평균적인 경우 탐색, 삽입, 삭제 연산에서 O(log ''n'')의 시간 복잡도를 나타낸다. 이는 데이터가 비교적 균등하게 분포되어 있을 때 효율적인 성능을 제공한다.그러나 최악의 경우, 데이터가 한쪽으로 편향되어 삽입될 때 트리의 높이가 ''n''에 가까워지면서 연결 리스트와 유사한 형태가 될 수 있다. 이 경우 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(''n'')까지 증가하여 성능이 저하된다.
이러한 성능 저하를 방지하고 최악의 경우에도 O(log ''n'')의 시간 복잡도를 보장하기 위해 AVL 트리, 레드-블랙 트리, B 트리와 같은 균형 잡힌 이진 탐색 트리들이 사용된다. 이 트리들은 데이터 삽입 및 삭제 과정에서 트리의 균형을 유지하는 추가적인 작업을 수행하여 효율적인 검색 성능을 유지한다.
이진 탐색 트리의 공간 복잡도는 저장하는 노드의 개수 ''n''에 비례하여 최악의 경우 O(''n'')이다.
4. 5. 기타 자료 구조
B-트리, 레드-블랙 트리와 같은 고급 자료 구조들은 데이터베이스 시스템 등에서 대용량의 데이터를 효율적으로 관리하는 데 유용하게 사용된다. 여러 자료 구조들의 시간 복잡도와 공간 복잡도는 다음과 같다.| 자료 구조 | 시간 복잡도 | 공간 복잡도 | |||||||
|---|---|---|---|---|---|---|---|---|---|
| 평균: 인덱싱 | 평균: 탐색 | 평균: 삽입 | 평균: 삭제 | 최악: 인덱싱 | 최악: 탐색 | 최악: 삽입 | 최악: 삭제 | 최악 | |
| 스킵 리스트 | O(log (n)) | O(log (n)) | O(log (n)) | O(log (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(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | 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(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(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(log (n)) | O(log (n)) | O(n) |
| K-d 트리 | O(log (n)) | O(log (n)) | O(log (n)) | O(log (n)) | O(n) | O(n) | O(n) | O(n) | O(n) |
참조
[1]
서적
Introduction to Algorithms
2001
[2]
간행물
Smoothed analysis: an attempt to explain the behavior of algorithms in practice
http://cs-www.cs.yal[...]
ACM
[3]
웹사이트
Worst-case complexity
http://www.fsz.bme.h[...]
2008-11-30
[4]
서적
Introduction to Algorithms
2001
[5]
웹인용
Worst-case complexity
http://www.fsz.bme.h[...]
2017-01-04
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com