점근적 분석은 다양한 알고리즘에서 성능을 비교할 때 사용되는 방법입니다. 각각의 알고리즘은 주어진 상황에 따라, 사용할 수 있는 메모리 용량과 소모되는 시간을 비교할 수 있습니다. 입력되는 데이터에 대해 시간복잡도를 수학적으로 측정하는 방법이 점근적 분석입니다.
사실 알고리즘의 성능을 비교할 때 시간 복잡도와 공간 복잡도를 비교할 수 있는습니다. 시간 복잡도는 알고리즘을 수행하는데 사용되는 시간, 공간 복잡도는 필요한 메모리의 양을 의미합니다.
일반적으로 알고리즘에 대해 이야기할 때, 공간 복잡도 보다는 시간 복잡도가 더 많이 언급됩니다. 그 이유는 다음과 같습니다.
- 메모리, 디스크 등의 자원은 하드웨어에 한정적이지만, 소프트웨어 측면에서 알고리즘에 따라 소모되는 시간은 크게 변할 수 있다.
- 공간적인 측면은 쉽게 재사용될 수 있지만, 소모되는 시간은 쉽게 핸들링할 수 있는 영역이 아니다.
- 공간의 사용량은 언제든지 확인할 수 있지만, 소모되는 시간은 즉각적으로 확인할 수 없다.
점근적 분석에서 시간 복잡도를 표기할 때 3가지 표기법이 있습니다. O(Big O), Ω(Omega), Θ(Theta)로 각각 상한, 하한, 내부를 의미합니다. 알고리즘을 비교할 때 최악의 상황을 고려해야하기 때문에 상한인 O를 가장 많이 고려합니다.
O(Big O)
- 알고리즘의 효율성을 표기해주는 표기법
- 최악의 상황을 고려해 알고리즘의 효율을 비교함
- 수학적 정의
n > n0인 모든 n에 대해 f(n) ≤ c·g(n)인 양수 c와 n0가 존재하면, f(n)을 O(g(n))이라고 나타낼 수 있다. - 빅오 표기의 시간복잡도 비교
O(1) < O(loglogn) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(3^n) < O(n!) < O(n^n)
주요 알고리즘의 시간복잡도
- 선택정렬: O(n²)
- 재귀호출 하노이탑: O(2^n)
- 탐색
순차탐색: O(n)
이진탐색: 정렬된 데이터, O(logn)
보간탐색: O(loglogn)
반복호출 피보나치 수열: O(n)
순환호출 피보나치 수열: O(2^n)
배열: O(1)
리스트: O(n)
정렬의 시간복잡도
- 삽입정렬은 데이터가 정렬되어 있을 때, 최선의 시간복잡도 O(n)을 가진다.
- 퀵정렬은 데이터가 정렬되어있거나 역순일 때, 최악의 시간복잡도 O(n²)을 가진다.
- 합병정렬은 제자리정렬(in-place sorting)이 아니다.
- 안정성은 같은 키값을 가진 데이터가 정렬이 적용되기 전후가 일치하는지를 의미한다.
- 위의 정렬들은 비교와 교환 정렬이고, 분할과 정복 방식으로 정렬한다. 이는 스택을 이용해서 정렬이 가능하다.
- 추가로 기수정렬의 시간복잡도는 O(d(n+r))이다. d: 자릿수, n: 데이터 수, r은 버킷의 수를 의미한다.
