점근 표기법 (asymptotic notation) 알아보기
점근 표기법(asymptotic notation)을 이해하고 대표적인 세 가지 유형의 점근 표기법인 빅오 표기법(Big-O notation), 빅 오메가 표기법(Big-Omega notation) , 빅 세타 표기법(Big-Theta notation)에 대해 알아보도록 하겠습니다.
점근 표기법 (asymptotic notation)
컴퓨터 알고리즘의 실행시간은 실행환경에 따라 다르게 측정됩니다.
ex) 하드웨어, 운영체제, 언어 등
실행환경을 동일하게 하는 것은 어렵기 때문에 기본 연산(산술 연산, 제어 연산 등)의 실행 횟수로 성능을 분석합니다.
연산의 실행 횟수는 입력 크기 n에 대한 함수로 표현합니다.
ex) \(f(n) = n^2+3n+1\)
함수가 복잡할수록 어느 알고리즘이 효율적인지 비교하는 것은 어려워지기 때문에 함수를 단순화하기 위해 점근 표기법을 사용합니다.
점근 표기법이란 함수를 단순화하여 함수의 증가율을 다른 함수와의 비교로 표현하는 방법입니다. 이것으로 시간과 공간 복잡도를 표현할 수 있습니다.
예를 들어 \(T(n) = n^2+3n+1\) 인 시간 복잡도를 \(n^2\) 와 \(3n+1\)로 나누어 그래프로 나타내면 다음과 같습니다.
n에 값이 증가할수록 \(3n+1\)에 값이 전체 시간 복잡도에 끼치는 영향은 미미하게 됩니다.
그러므로 n에 값이 무한히 증가할수록 \(n^2 + 3n + 1\) 그래프는 최고차항인 \(n^2\) 그래프와 점근적으로 가까워지게 됩니다.
즉, n에 값이 증가할수록 최고차항 이하의 값들은 함수 증가율에 큰 영향을 끼치지 않습니다.
이렇듯 점근 표기법은 함수의 증가율에 따른 다른 함수와 비교를 하는 것이 목표이기 때문에 최고차항을 제외한 모든 항과 최고차항의 계수는 무시합니다.
예를 들어 다음과 같은 알고리즘을 비교한다고 하겠습니다.
알고리즘 1 - \(T(n) = 10000n + 20000\)
알고리즘 2 - \(T(n) = n^2 + 3n + 1\)
한 번에 어느 알고리즘이 효율적인지 판단하기는 어렵습니다.
이것을 점근 표기법인 빅오로 표현하면 다음과 같습니다.
알고리즘 1 - \(T(n) = O(n)\)
알고리즘 2 - \(T(n) = O(n^2)\)
점근 표기법으로 인해 알고리즘 1 이 알고리즘 2보다 연산 실행 횟수가 적기 때문에 효율적이라는 것을 쉽게 확인할 수 있습니다.
대표적으로 세 가지 유형의 점근 표기법이 있습니다.
- 빅오 (O)
- 빅 오메가 (Ω)
- 빅 세타 (Θ)
이 중 가장 많이 쓰이는 것은 빅오 표기법입니다. 왜냐하면 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해볼 수 있기 때문입니다.
빅오 표기법 (Big-O notation)
빅오 표기는 다음과 같이 표시합니다.
$$ f(n) = O(g(n)) $$
이때 g(n)을 함수 f(n)의 점근적 상한(asymptotic upper bound)이라고 합니다.
즉 f(n)의 복잡도는 최악의 경우라도 g(n) 보다 작거나 같다는 의미입니다. (f(n) ≤ g(n))
- 알고리즘 성능이 최악의 경우라도 g(n) 이상이라는 의미
이를 수식으로 나타내면 다음과 같습니다.
$$ O(g(n)) = \{ f(n): n ≥ n_0 인\,모든 n에\,대해 0 ≤ f(n) ≤ cg(n)을\,만족하는\,양수\,상수 c와 n_0가\,존재 \} $$
빅 오메가 표기법 (Big-Ω notation)
빅 오메가 표기는 다음과 같이 표시합니다.
$$ f(n) = Ω(g(n)) $$
이때 g(n)을 함수 f(n)의 점근적 하한(asymptotic lower bound)이라고 합니다.
즉 f(n)의 복잡도는 최선의 경우라도 g(n) 보다 크거나 같다는 의미입니다. (f(n) ≥ g(n))
- 알고리즘 성능이 아무리 빨라도 g(n) 이하라는 의미
이를 수식으로 나타내면 다음과 같습니다.
$$ \mathsf{\Omega}(g(n)) = \{ f(n): n ≥ n_0 인\,모든 n에\,대해 0 ≤ cg(n) ≤ f(n) 을\,만족하는\,양수\,상수 c와 n_0가\,존재 \} $$
빅 세타 표기법 (Big-Θ notation)
빅 세타 표기는 다음과 같이 표시합니다.
$$ f(n) = \mathsf{\Theta}(g(n)) $$
이때 g(n)을 함수 f(n)의 점근적 상한 및 하한(asymptotic tight bound)이라고 합니다.
즉 f(n)의 복잡도가 최선의 경우나 최악의 경우라도 g(n) 범위 내에 있다는 의미입니다. (대략 f(n) = g(n))
- 알고리즘 성능이 g(n)의 상한과 하한에 포함한다는 의미
이를 수식으로 나타내면 다음과 같습니다.
$$ \mathsf{\Theta}(g(n)) = \{ f(n): n ≥ n_0 인\,모든 n에\,대해 0 ≤ c_1g(n) ≤ f(n) ≤ c_2g(n) 을\,만족하는\,양수\,상수 c_1, c_2와 n_0가\,존재 \} $$
