1. 시간 복잡도 (Time Complexity)
ㅇ 알고리즘을 실행하는데 필요한 시간 척도
ㅇ 시간 복잡도는, 알고리즘 효율성을 판단하는 중요 척도 (시간 복잡도, 공간 복잡도) 중 하나임
- 입력 값의 개수에 따른 알고리즘 수행 예측 시간을 바탕으로,
- 알고리즘의 상대적인 효율성을 평가하는 실행 시간 분석법
2. 시간 복잡도의 특징
ㅇ 시간 복잡도의 산정 기준 : 연산 수
- 소요되는 기본 연산 수에 의거함
. 주로, 알고리즘이 사용한 기본 연산의 수(명령 수,스텝 수)에 따름
. 여기서, 주요 기본 연산으로는, 데이터의 비교,덧셈,곱셈,나눗셈 등이 있음
ㅇ 시간 복잡도의 표현 방식 : 함수적
- 입력 크기에 대한 함수적 관계를 나타냄
. 여기서, 입력 크기의 例는,
.. 정렬을 하려는 경우 : 정렬 대상이 되는 원소의 수
.. 계승 계산을 하는 경우 : 계승 계산을 하고자 하는 자연수
.. 최단거리를 구하는 경우 : 노드의 수 및 간선의 수
- 따라서,
. 기본 연산 수가 입력 크기(n : 입력의 개수)와 어떤 함수 관계가 있는가를 분석하고,
. 이를 함수식 처럼 표현하여 봄
ㅇ 시간 복잡도의 분석 방법 : 점근적 (Asymptotic)
- 입력 크기가 무한히 증가할 때, 알고리즘이 어떻게 작동하는가에 대해서 따질 때,
- `점근적 분석 방법`을 씀
. 상계/상한(최악,빅 오), 하계/하한(최선,빅 오메가), 평균(빅 세타)
* 이들 모두를 `점근적 표기법` 이라고 총칭하기도 함
ㅇ 시간 복잡도의 분석 종류 : (아래 3.항 참조)
- (최악의 경우) => big-O (빅 오 표기법) : O() => `최악, 이정도는 보장` (점근적 상한선)
. (aymptotic upper bound)
- (최선의 경우) => big-Omega (빅 오메가 표기법) : Ω() => `최고 수준` (점근적 하한선)
. (aymptotic lower bound)
- (평균의 경우) => big-Theta (빅 세타 표기법) : Θ() => `대략` (점근적 치밀 경계)
. (aymptotic tight bound)
ㅇ 시간 복잡도의 계산 방식 : (주로, 빅 오 표기법에 준함)
- 전체 값 계산에 가장 큰 영향을 주는 항 만 고려함 (즉, 최악의 시나리오)
- 즉, 근사적인 것을 구함
3. 시간 복잡도의 분석 종류
ㅇ (최악의 경우, worst case)
- big-O (빅 오 표기법) : O() => `기껏해야`
. 점근적 상한선
.. 입력 크기가 무한대로 갈 때 점근적 상한
.. (아무리 나빠도 시간이 이보다 덜 걸림. 즉, 최악의 시나리오)
. 주로, 빅 오 표기법을 사용함
ㅇ (최선의 경우, best case)
- big-Omega (빅 오메가 표기법) : Ω()=> `적어도`
. 점근적 하한선
.. (최소 이만한 시간이 걸림, 최선의 시나리오)
ㅇ (평균의 경우, average case)
- big-Theta (빅 세타 표기법) : Θ() => `대략`
. 점근적 상하한
. 빅 오,빅 오메가 표기법의 절충 (즉,교집합)
4. 시간 복잡도의 주요 계산 例
ㅇ 가장 큰 차수 만 고려 : 例) n2 + n + 1 => O(n2)
ㅇ 계수는 1 로 함 : 例) 3n => O(1n) => O(n)
ㅇ 작은 차이는 무시 : 例) O(n-1) => O(n)
ㅇ 규모가 큰 것 만 고려 : 例) O(2n + n2) => O(2n)
5. 시간 복잡도의 주요 표기 例)
※ 시간 복잡도가, 입력 크기의 함수적 관계식으로 표현되면서,
- 이때 함수의 증가율을 특징지울 수 있는 여러 부류들이 아래와 같음
※ ☞ 시간복잡도 표기 예 참조
- O(c) 또는 O(1) : 상수 시간 알고리즘 (constant time algorithm)
- O(log n) : 로그 시간 알고리즘 (logarithmic time algorithm)
- O(n) : 선형 시간(1차 시간) 알고리즘 (linear time algorithm)
- O(n log n) : n 로그 시간 알고리즘 (nlogn time algorithm)
- O(n2) : 평방 시간(2차 시간) 알고리즘 (quadratic time algorithm)
- O(n3) : 3차 시간 알고리즘
- O(2n) : 지수 시간
- O(n!) : 계승 시간 (Factorial Time Algorithm)
- O(∞) : 종료되지 않는 무한 루프
※ [참고] 시간복잡도 연산 크기 순서 例)
- O(1) < O(log n) < O(n) < O(n logn) < O(n2) < O(n3) < O(2n) < O(n!) < O(∞)