Overview

알고리즘을 구현할 때, 가장 중요한 것은 정확성이다. 정확성이 만족된다면, 연산 속도를 점검해야 한다. 연산 속도를 나타내는 개념을 Time Complexity라고 하고, 이를 지표로 나타낸 것이 Asymptotic Notation이다.

시간 복잡도(Time Complexity)

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 나타낸다. 이를 점근 표기법으로 표현하며, 주로 Big-O notation을 사용한다.

Why Big-O?

worst case를 파악하여 알고리즘을 개선하거나 최악을 피하기 위해 Big-Omega notation보다 Big-O notation를 주로 사용한다.

점근 표기법(Asymptotic Notation)

점근 표기법은 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 정수론(Number theory)와 해석학(Mathmetical analysis)의 방법이다.

• 계수와 낮은 차수의 항을 제외시킨다.
  • $4n+2 → O(n)$
• 근사치를 최대한 좁혀서 표현한다.
  • “$7n-3$은 $O(n^3)$이다”라는 표현은 틀리지는 않았으나, “$7n-3$은 $O(n)$이다”라고 표현하는 것이 더 좋은 설명이다.

복잡성(Complexity)

크기가 n인 입력에 대하여,

1. $O(1)$: $n$에 관계없이 일정 시간 이하에 수행되는 알고리즘
2. $O(log\ n)$: $\log_2 n$에 비례하는 시간 이하에 수행되는 알고리즘 (e.g. 이진 탐색)
3. $O(n)$: $n$에 비례하는 시간(선형시간) 이하에 수행되는 알고리즘 (e.g. 선형 탐색)
4. $O(n\ log\ n)$: $n$에 대략 비례할 수 있는 시간 이하에 수행되는 알고리즘 (e.g. 비교정렬, FFT)
5. $O(n^2)$: $n^2$에 비례하는 시간 이하에 수행되는 알고리즘 (e.g. LCS)
6. $O(n^3)$: $n^3$에 비례하는 시간 이하에 수행되는 알고리즘 (e.g. 행렬의 곱셈)
7. $O(a^n)$: $2^n$과 같은 꼴의 수행 시간(지수시간) 이하에 수행되는 알고리즘
8. $O(n!)$: $n!$과 같은 꼴($n^n$)의 수행 시간 이하에 수행되는 알고리즘