점근적 표기법
작성일 10/23 최초 작성.
들어가며
학습 목표
- 점근적 표기법의 개념과 종류, 그 특징을 살펴본다.
- 점근적 표기법의 장점과 한계를 살펴본다.
학습 상황
- 알고리즘을 순차적으로 학습하며, 점근적 표기법이 가지는 장점과 한계가 궁금해졌다.
점근적 표기법이란?
점근적 표기법의 개념
-
점근적 표기법(asymptotic notation)은 알고리즘 분석과 성능 측정에 이용하는 표기법이다. 주로 시간 복잡도와 공간 복잡도를 함수 형태로 표현한다.
-
왜 ‘점근적’인가?
: 입력의 크기가 아주 커지는 경우에서 알고리즘의 동작을 설명하기 위함이다. 즉, 입력값의 크기에 따른 함수와 그 함수가 얼마나 빠르게 커지는 지(성장률, rate of growth)를 살펴보기 위해서다.
점근적 표기법의 종류와 특징
- 빅-오 표기법
-
빅-오(big-O) 표기법은 점근적 상한선을 나타낸다. 즉, 알고리즘에서 최악의 경우를 나타낸다.
-
f(n) = O(g(n)) 은 점근적 증가율이 g(n)을 넘지 않는 모든 함수들의 집합이다. 즉, g(n) 내 최고차항의 차수가 k일 때, 최고차항의 차수가 k 이하인 함수 f(n)은 모두 O(g(n))이다.
-
O(g(n)) = {f(n): 모든 n ≥ n0, 양의 상수 c 존재, c * g(n) ≤ f(n)}
- 빅-오메가 표기법
-
빅-오메가(big-Ω) 표기법은 점근적 하한선을 나타낸다. 즉, 알고리즘에서 최선의 경우를 나타낸다.
-
f(n) = Ω(g(n)) 은 점근적 증가율이 g(n)을 넘는 모든 함수들의 집합이다. 즉, g(n) 내 최고차항의 차수가 k일 때, 최고차항의 차수가 k 이상인 함수 f(n)은 모두 Ω(g(n))이다.
-
Ω(g(n)) = {f(n): 모든 n ≥ n0, 양의 상수 c 존재, c * g(n) ≥ f(n)}
- 빅-세타 표기법
-
빅-세타(big-Θ) 표기법은 점근적 상한선과 점근적 하한선의 교집합을 나타낸다. 즉, 알고리즘은 빅-세타 표기법의 함수 범위 내에서 동작한다.
-
Θ(g(n))은 O(g(n))과 Ω(g(n))에 모두 속하는 함수들의 집합이다.
-
Θ(g(n)) = {f(n): 모든 n ≥ n0, 양의 상수 c1, c2 존재, c1 g(n) ≤ f(n) ≤ c2 g(n)}
+) 리틀-오, 리틀-오메가 표기법
-
리틀-오, 리틀-오메가 표기법은 각각의 ‘빅’ 표기법과 비슷하나, 함수 집합에 해당 표기법 내 함수 g(n)과 최고 차항의 차수가 같은 함수는 포함되지 않는다.
-
이들은 각각 표기법의 ‘여유있는 상한’과 ‘여유있는 하한’을 의미한다. 점근적 의미에서 더 작거나, 더 커서 g(n)을 압도하거나 g(n)에 압도당하는 함수들의 집합이다.
점근적 표기법의 장점과 한계
점근적 표기법의 장점
- 효율성
: 점근적 표기법은 크기가 큰 입력에서, 알고리즘의 성능을 간편하게 비교할 수 있게 만든다.
점근적 표기법의 한계
- 외부 요소 무시
: 점근적 표기법은 입력 크기에 따른 성능만을 고려하기에, 다양한 조건 하에서의 실제 환경에서는 알고리즘 성능이 다르게 나올 수가 있다.
참고 자료
문병로 (2013), ”쉽게 배우는 알고리즘“: 한빛아카데미.
칸 아카데미 https://ko.khanacademy.org/computing/computer-science/algorithms/asymptotic-notation/a/asymptotic-notation
