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