공통
표기법
//시간복잡도의 판단 기준에 대한 내용 첨가 필요,
점근적 표기법 3가지
- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
평균적인 세타 표기를 통한 시간복잡도 예측을 하는 게 좋지만, 평가하기가 까다로워 일반적으로 빅오 표기법을 많이 사용하며, 최악의 상황을 고려하니 평균과 가까운 성능으로 예측하기 쉽다.
빅오 표기법 (Big-O)
정의
빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.
- 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
- 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다. (근대에는 메모리 용량의 증가로 중요도가 낮아졌다.)
Big-O 복잡성 차트
시간복잡도
정의
말 그대로 문제를 해결하는데 걸리는 시간,
왜 실행시간이 아닌 연산수치로 표현할까? → 이는 컴퓨터의 사양마다 처리속도는 천차만별이기 때문에 성능을 고려하지 않은 명령어의 실행횟수만을 고려하는 것이다.
시간복잡도에서 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다.
방법) 상수를 제거하고 최고 차항만 남긴다.
복잡도 단위
| 명령어 실행횟수 | 최종 시간복잡도 |
| 1 | O(1) |
| 2n + 20 | O(n) |
| 3n² | O(n²) |
시간복잡도 별 문제해결 단계
| 시간복잡도 | 개념적 시간 | 설명 |
| O(1) |
상수 시간 | 오직 한번의 단계로 처리 |
| O(log n) | 로그 시간 | 문제 해결을 위한 단계를이 연산마다 특정 요인에 의해 줄어듬 |
| O(n) | 직선적 시간 | 문제 해결하기 위한 단계의 수가 입력값 n만큼의 횟수를 거침 |
| O(n log n) | 선형 로그형 단계를 거침 (부가설명 필요) | |
| O(n²) | 2차 시간 | 문제를 해결하기 위한 단계의 수는 입력값의 n의 제곱 |
| O(Cⁿ) | 지수 시간 | 문제를 해결하기 위한 단계의 수는 주어진 상수값 C의 n 제곱 |
| O(n!) | 팩토리얼 시간 | 문제 해결의 단계 수는 팩토리얼 수준 |
시간 복잡도 별 예제
| 시간복잡도 | 예제 |
| O(1) | 단순 출력 및 연산 |
| O(log n) | 효율좋은 검색 알고리즘 |
| O(n) | 입력된 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 (1차 배열 순회) |
| O(n log n) | 효율좋은 정렬 알고리즘 (상세 설명 추가 필요) |
| O(n²) | 이중 루프 |
| O(Cⁿ) | 데이터 갯수 만큼 중첩 루프 |
| O(n!) | |
시간복잡도 계산법
**계산법**
for(let i=0; i < n; i++) { // 이 때 실제로 로직은 n번 실행되지만, 조건의 검증을 위한 마지막 i == n 인 경우 까지 포함하여, **(n + 1)** 회로 간주한다.
if(...) ~ // 해당 영역은 위 조건에 부합하는 프로세스만 실행 되므로 n 회이다.
for(let j=0; j < i ; j ++) { // {i 루프 횟수 (n)} * {j 루프 최대 가능 횟수 n (i == n) + 마지막 검증 단계 + 1} ==> **최종 n * (n + 1)**
... // n * n
}
}시간 복잡도의 계산은 모든 행의 복잡도를 더한 값에서 최고 차항의 계수를 지운 값을 나타낸다.
(n + 1) + n + (n * (n+1)) + (n * n) = 2n² + 3n + 1 = n²
log N 시간복잡도
2개의 자식 노드를 가지는 이진트리를 이용해서 M개의 노드 중 원하는 값의 노드를 찾는다고 해보자. 처음에는 M개의 노드 모두 탐색 대상이지만,
루트 노드에서 M / 2 ⇒ M / 4 ⇒ M / 8 이런식으로 점진적으로 ½로 줄어들게 된다.
만약, 탐색을 해야하는 자료의 수가 2ⁿ 개라면, 이진 트리를 사용할 경우 n 번의 탐색을 통해서 원하는 값을 찾을 수 있다. 이를 수식으로 나타내면,
$log_2(2^n) = n$ 이다.
이를 일반화하면, 각 노드의 자식 노드가 M개인 트리에서, N개의 자료 중 원하는 자료를 탐색하는 알고리즘의 시간 복잡도는
$log_m n 이다.
공간복잡도
정의
문제를 해결할 때 필요한 공간적인 자원, 필요로 하는 메모리양에 대한 지표