점근 표기법
Asymptotic notation, 漸近表記法
1. 개요 및 정의
수리과학의 여러 분야에서 함수의 증감 추세를 비교하는 표기법이다. 큰 O-표기법(Big-O notation), 란다우 표기법(Landau notation)이라 부르기도 한다.
무한대 점근의 정의는 실수열 $$f,g : \mathbb{N} \rightarrow \mathbb{R}$$에 대해서도 동일하게 정의될 수 있고, 이 편이 훨씬 많이 쓰인다.'''점근 표기법(asymptotic notation)'''
실함수 [math(f,\,g: [0,\,\infty) \rightarrow \mathbb{R})]에 대해
1. 상수 $$M>0,\,c>0$$가 존재하여 $$x>M \Rightarrow |f(x)| \le c g(x) $$를 만족시킬 때, 이를 "$$x \rightarrow \infty$$에 대해 $$f(x) = O(g(x)) $$"라 표기한다.
1. 상수 $$\epsilon>0,\,c>0$$가 존재하여 $$|x-a|<\epsilon \Rightarrow |f(x)| \le c g(x) $$를 만족시킬 때, 이를 "$$x \rightarrow a$$에 대해 $$f(x) = O(g(x)) $$"라 표기한다.
수식 입력 편의상 이탤릭체를 사용하는 경우가 대부분이나, 흘림체인 $$\mathcal{O}$$를 사용하는 경우도 많이 있다. 다만, $$O$$를 처음 사용한 버크만, 란다우의 서적이나 이를 컴퓨터 과학에 본격적으로 들여온 도널드 크누스의 노트도 딱히 글꼴을 지정하진 않았다.
1.1. 연관된 표기법
크누스는 란다우의 표기법을 종합해 다음의 4가지 표기법을 같이 정리하였다.
- $$f(x) = o(g(x)) $$: 임의의 $$c>0$$에 대해 $$M$$이 존재하여 $$x>M \Rightarrow |f(x)| \le c g(x) $$
- $$f(x) = \Omega(g(x)) $$: $$M,c>0$$이 존재하여 $$x>M \Rightarrow |f(x)| > c g(x) $$
- $$f(x) = \omega(g(x)) $$: 임의의 $$c>0$$에 대해 $$M$$이 존재하여 $$x>M \Rightarrow |f(x)| > c g(x) $$
- $$f(x) = \Theta(g(x)) $$: $$f(x)>0$$ 중에서 $$f(x)=O(g(x)) $$이며 $$f(x)=\Omega(g(x)) $$
이외에도 점근을 나타내는 다음의 다양한 표기가 있다.
- 표기 $$f \ll g$$는 $$f=O(g) $$와 동치이다.
- 표기 $$f \asymp g$$는 $$f = \Theta(g) $$와 동치이다.
- 표기 $$f \sim g$$는 $$\lim_{x\to\infty}\limits (f/g)=1$$과 동치이다.
2. 해석학에서의 활용법
극한과 비슷하게 생각할 수 있지만 세부적인 성질은 달라지는 것들이 많다. 예를 들어서
$$\lim_{x\to\infty}\limits \left|\dfrac fg\right| < \infty \Rightarrow f = O(g) $$
$$\displaystyle f =O(g) \Leftrightarrow \limsup \left| \frac{f}{g} \right| < \infty $$
$$\displaystyle $$
해석학에서의 점근 표기법은 단순히 $$f=O(g)$$꼴 뿐만이 아니라 굉장히 자유롭게 쓰이는데, 예를 들어서$$\displaystyle \sum_{i=1}^N \frac1i = \log N + \gamma + O(N^{-1}) $$ ($$N \rightarrow \infty$$일 때)
$$e^x = 1 + x + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \cdots + \dfrac{x^k}{k!} + O(x^{k+1}) $$ ($$k$$는 고정된 자연수이고 $$x \rightarrow 0$$일 때)
O-표기법은 다변수함수, 벡터함수, 복소함수 등에서 쓰이기도 한다. 예를 들어서, 다변수 테일러 정리의 표현식을 다음처럼 쓸 수 있다.
$$\displaystyle f(x+h) = \sum_{|\alpha| \le m} \frac{\partial^{\alpha} f(x)}{\alpha_1! \cdots \alpha_n!}h^{\alpha} + O(\|h\|^{m+1}) $$
3. 컴퓨터 과학에서의 점근 표기법
일반적으로 알고리즘의 시간복잡도를 나타내는데 사용된다. Big-O 표기법은 알고리즘이 해당 차수이거나 그보다 낮은 차수의 시간복잡도를 가진다는 의미이다. 물론 공간복잡도에 대해서도 사용될 수 있다.
프로그램을 돌렸을 때, 프로그램이 돌아가는 '''정확한 단계(step)의 수를 결정하는 작업은 매우 어렵다'''. 단계 수를 정확히 결정하는 데 드는 비용은 '단계'의 개념 자체가 부정확하기 때문에 낭비를 초래할 수 있다.[1] 그런데, 입력 데이터 개수 $$n$$에 대해 두 프로그램의 단계 차이가 $$5n+7$$이라든가 $$n^2+25$$인 경우는 비교의 가치가 생긴다. 그러나, 이 경우에도 마찬가지로 굳이 사용자가 $$5n+7$$이라는 것을 정확히 알기 보다는 그냥 $$5n$$ 정도라고 생각해도 되지 않을까? $$n$$이 10억 정도라면 반드시 '예, 이 프로그램은 10억 개를 넣으면 50억 7개의 스텝을 진행합니다.'라고 얘기해야 하는가? 그냥 '대략 $$5n$$ 정도 필요하구나' 하고 인식하면 충분히 큰 $$n$$에 대해서는 그게 그거라는 것을 알 수 있다. 마찬가지로, 굳이 $$5n$$이라고 하기보다는 '아, $$n^1$$에 비례하는구나, $$n^2$$에 비례하는구나' 정도로 생각해도 충분하다는 것이다.
결국, 정의와 연관시켜서 생각하면, $$O(5n+7)=O(5n)=O(n) $$이 되고, $$O(n^2+25)=O(n^2) $$이 된다는 뜻이다. 여기서 등호 기호($$=$$) 기호를 '같다(equals)'가 아니라 '~이다(is)', '~쯤 된다'라고 해석하면 기호의 혼란을 피할 수 있다. 경우에 따라 $$O(g(n)) $$을 하나의 집합으로 보고 $$f(n) \in O(g(n)) $$으로 표기하기도 한다.[2]
[image]
<파이썬 알고리즘 인터뷰> p.100, 책만, 2020
간단한 예를 한번 들어보자. 디스크에 있는 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자. 그림에서 파일 크기가 작다면, 즉 $$n$$이 작다면 $$O(n)$$의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달 하는게 더 빠를 수 있다(비용은 고려하지 않는다면).[3] 파일이 아무리 커도, 즉 $$n$$이 아무리 커도 비행기를 통한 파일 전송은 $$O(1)$$로 항상 일정한 시간이 소요되기 때문이다. 이것이 바로 점근적 실행 시간이며, 빅오는 점근적 실행 시간을 표기하는 방법 중 하나다.
4. 참고
5. 관련 문서
[1] 명령문 $$x=y$$와 $$x=y+z+(x/y)+(x*y*z-x/z)$$는 둘 다 한 단계로 간주한다.[2] 대다수의 알고리즘 원서가 이 집합(set)개념을 사용하고 있다. 보다 수학적으로 엄밀해지고, asymptotic tight bound을 정확히 특정하는 Big-θ 표기법에서는 $$\theta(g(n)) $$을 간단히 $$O(g(n))\cap\Omega(g(n)) $$으로 정의할 수 있다. $$f(n)=O(g(n)) $$에서 등호는 $$\in$$의 의미를 imply하며 동시에 직관성을 얻는다. 이 '같다'의 직관성은 Big-O notation의 오용을 초래했고, Big-Theta notation을 탄생하게 한 배경이 되었다.[3] 실제로 구글등의 PB단위로 데이터를 취급하는 단체,업체들이 이렇게 데이터를 항공운반 하는경우가 자주 있다.