1. 시간 복잡도란
: 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는지를 나타낸다. 수행시간은 1억번의 연산을 1초의 시간으로 간주하여 예측한다.
(+) 시간복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외한다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
2. 시간 복잡도 유형
- O(n) (big-O) : 알고리즘의 복잡도의 상한, 주로 사용
- Θ(n) (big-Theta) : 알고리즘의 빅오와 빅오메가의 평균
- Ω(n) (big-Omega) : 알고리즘의 복잡도의 하한
3. 빅 오
- O(1) : 문제를 해결하는데 오직 한 단계만 처리하는 경우
- O(logn) : 필요한 단계들이 연산마다 줄어드는 경우.
- O(n) : 단계의 수와 입력값 n이 1:1 관계를 가지는 경우.
- O(nlogn) : 단계의 수가 N*(logN) 번만큼의 수행시간을 가지는 경우.
- O(n^2) : 댠계의 수에 따라 수행시간이 n의 제곱형태인 경우.
- O(2^n) : 주어진 상수값 2 의 n 제곱형태인 경우.
- 𝑂(𝑛!) : 팩토리얼 형태인 경우.
(아래에 있을 수록 오래 걸린다!)
- 입력값을 넣어 비교 출처
- 그래프로 보여주는 비교 출처
