점근 표기법

1 개요

계산 복잡도 이론에서 사용되는 점근 표기법. 컴퓨터 과학에서는 주로 입력 데이터의 크기와 알고리즘의 소요 시간 또는 메모리의 상관관계를 나타내지만, 엄밀히는 임의의 함수에 대하여 "함수의 입력값(정의역의 원소)이 커짐에 따라 그 출력값(그 원소의 상)이 얼마나 빠르게 커지는가"를 표현한다. 예를 들어, n개의 자연수를 병합 정렬로 정렬하기 위해서는

[math]O\left(n \lg n\right)[/math]의 시간이 소요된다.
[math]O\left(n\right)[/math]의 공간을 사용한다.
[math]O\left(1\right)[/math]개의 달걀(일정한 수, 즉 0)을 먹어야 한다.

와 같은 명제는 모두 참이다. 그러나 알고리즘을 평가할 때는 대체로 그 시간과 공간의 사용량이 주된 관심사가 되고 그 중에서도 특히 시간에 신경을 많이 쓰기 때문에, "병합 정렬은 [math]O\left(n \lg n\right)[/math] 알고리즘이다"와 같은 말을 할 때는 [math]O\left(n \lg n\right)[/math]이 무엇과 무엇의 관계를 나타내는지를 따로 말하지 않는 이상은 그 입력값의 크기와 소요 시간의 관계를 이야기한다고 봐도 무방하다.

2 정의

[math]f\left(x\right)[/math]와 [math]g\left(x\right)[/math]인 두 함수를 실함수로 정의하자.
충분히 큰 모든 [math]x[/math]에 대해서
[math]\left|f\left(x\right)\right| \leq M\left|g\left(x\right)\right| [/math] ([math]x \gt x_0[/math])를 만족하는 양수인 실수[math]M[/math]과 실수[math] x_0[/math]가 존재하는 경우에만
[math] f\left(x\right) = O\left(g\left(x\right)\right) [/math] 이다.

이것은 실수 [math]a[/math]에 충분히 가까운 [math]x[/math]에 대해서 [math]g(x)[/math]가 0이 아닐 때, [math]\displaystyle \lim_{x\to a} \left|\frac{f(x)}{g(x)}\right| \lt \infty[/math]과 동치이다.

직관적으로 [math]f\left(x\right)[/math]의 상승률이 [math]g\left(x\right)[/math]의 상승률보다 클 수 없음을 나타낸다.

3 설명

프로그램을 돌렸을 때, 프로그램이 돌아가는 정확한 단계(step) 수를 결정하는 작업은 매우 어렵다. 단계 수를 정확히 결정하는 데 드는 비용은 '단계'의 개념 자체가 부정확하기 때문에 낭비를 초래할 수 있다.^[1] 그런데, 입력 데이터 개수 n에 대해 두 프로그램의 단계 차이가 [math]5n+7[/math]이라든가 [math]n^{2}+25[/math]인 경우는 비교의 가치가 생긴다. 그러나 이 경우에도 마찬가지로 굳이 사용자가 [math]5n+7[/math]이라는 것을 정확히 알기 보다는 그냥 [math]5n[/math] 정도라고 생각해도 되지 않을까? [math]n[/math]이 10억 정도라면 반드시 '예, 이 프로그램은 10억 개를 넣으면 50억 7개의 스텝을 진행합니다' 라고 얘기해야 하는가? 그냥 '대략 [math]5n[/math] 정도 필요하구나' 하고 인식하면 충분히 큰 [math]n[/math]에 대해서는 그게 그거라는 것을 알 수 있다. 마찬가지로, 굳이 [math]5n[/math]이라고 하기보다는 '아, [math]n^1[/math]값에 비례하는구나, [math]n^2[/math]에 비례하는구나' 정도로 생각해도 충분하다는 것이다.

결국 정의와 연관시켜서 생각하면 [math]O\left(5n+7\right) = O\left(5n\right) = O\left(n\right)[/math]이 되고, [math]O\left(n^2+25\right)=O\left(n^2\right)[/math]이 된다는 뜻이다. 여기서 = 기호를 '같다(equals)'가 아니라 '~이다(is)', '~쯤 된다'라고 해석하면 기호의 혼란을 피할 수 있다. 경우에 따라 [math]O\left(g\left(n\right)\right)[/math]을 하나의 집합으로 보고 [math]f\left(n\right) \in O\left(g\left(n\right)\right)[/math]으로 표기하기도 한다.

일반적으로 알고리즘의 시간복잡도를 나타내는데, Big-O 표기법은 해당 알고리즘의 시간 복잡도 중 해당 차수의 시간복잡도를 알고리즘이 가지거나, 혹은 그 보다 더 낮은 차수의 시간복잡도의 알고리즘을 가진다는 이야기인데..

쉽게 풀어 설명하면, 알고리즘의 성능을 결정하는 시간복잡도는 아래 순이다.
(위로 갈수록 간단하고, 아래로 갈수록 복잡해지며, [math]\lg N[/math]은 [math]\log_{2}N[/math]을 뜻한다)

[math]O\left(1\right)[/math] 과 같은 상수형태
[math]O\left(\lg n\right)[/math] 과 같은 로그 형태
[math]O\left(n\right)[/math] 과 같은 선형^[2]
[math]O\left(n \lg n\right)[/math] 과 같은 선형로그 형태
[math]O\left(n^2\right)[/math], [math]O\left(n^3\right)[/math]과 같은 다차 형태
[math]O\left(2^n\right)[/math], [math]O\left(3^n\right)[/math]과 같은 지수 형태^[3]
[math]O\left(n!\right)[/math] 과 같은 팩토리얼

여기서, 일반적으로 위로 갈수록 알고리즘이 매우 빨라지며, 아래로 갈수록 [math]n[/math]의 값이 커질 때 마다, 급격하게 알고리즘의 수행 시간이 증가한다.

예를 들어 [math]n[/math]에 대한 [math]O\left(1\right)[/math], [math]O\left(\lg n\right)[/math], [math]O\left(n\right)[/math], [math]O\left(n \lg n\right)[/math], [math]O\left(n^2\right)[/math], [math]O\left(n^3\right)[/math], [math]O\left(2^n\right)[/math], [math]O\left(n!\right)[/math]를 나열하여 비교하면,

1	1	1	1	1	1	1	1	1	1
lg n	0	1	1.58	2	3	4	5	6	9.97
n	1	2	3	4	8	16	32	64	1000
n lg n	0	2	4.75	8	24	64	120	384	9966
n²	1	4	9	16	64	256	1024	4096	1000000
n³	1	8	27	64	512	4096	32768	262144	1000000000
2ⁿ	2	4	8	16	256	65536	4294967296	약 1844경	약 1.07 x 10³⁰¹
n!	1	2	6	24	40320	20922789888000	약 2.63 x 10³⁵	약 1.27 x 10⁸⁹	약 4.02 x 10²⁵⁶⁷

[math]n[/math]의 값이 적을 때는 알고리즘 사이 큰 차이가 없고, 심지어 시간복잡도가 복잡한 알고리즘이 시간복잡도가 낮은 알고리즘보다 부분적으로 빠른 경우도 있지만, 보다시피 [math]n[/math]이 값이 커지면 커질수록, 시간복잡도가 복잡한 알고리즘은 수행시간이 급격하게 길어지게 된다. ^[4]

비슷한 형태의 시간복잡도를 가진 함수는 사실 큰 차이가 없지만, 시간복잡도 함수의 형태 자체가 다르면 바로 신세계가 열리는 것을 볼 수 있다. [math]n=64[/math]일 때, [math]n^2[/math]와 [math]n^3[/math]은 [math]64[/math]배 차이가 나지만^[5], [math]n^2[/math]와 [math]2^n[/math]의 차이는 어마어마한 것을 보라.^[6]

이로 인해서인지, 매우 작은 수의 [math]n[/math] 값만이 입력값으로 들어오는 몇몇 특별한 알고리즘이 아닌 이상, 지수급 이상의 시간복잡도를 가지는 알고리즘은 어느 정도 큰 [math]n[/math] 값이 입력으로 들어올 때 성능이 급격하게 떨어지므로 지양하게 된다. 특히 팩토리얼 값 이상이 되면 거의 써먹을 수가 없다. 스털링 근사를 이용하면 [math]n!\sim\left(n/e\right)^{n}[/math]이므로 억지로 만든다면야 팩토리얼 이상의 [math]O\left(n^{n^{n^{\cdots}}}\right)[/math] 형태의 시간복잡도를 가진 루프를 만들 수도 있지만, 일반적으로 알고리즘을 다룰 때에는 전수조사보다 효율적인 것만 다루는데, 대개의 경우 전수조사가 [math]O\left(n!\right)[/math]이라 [math]n^n[/math] 같은 것은 다루지 않는다.^[7]

이것을 또 뒤집어 말하면, 알고리즘을 어떻게든 연구해서 개선해서, 예를 들어 [math]2^n[/math]과 같은 지수형태의 알고리즘의 코드를 개선해 [math]n^x[/math] 형태로만 어떻게 개선한다면 알고리즘의 엄청난 성능 향상을 기대할 수 있다는 말.

이런 고로, 프로그래밍 등에서 보통 알고리즘 과목은 전공필수 내지 공학인증필수 과목으로 지정되고 있다. 그만큼 중요하고, 알아 두면 쓸 곳이 많기 때문. ~~배우는 사람에게는 전혀 와닿지 않는 말이지만 말이지~~

하지만 정작 이쪽 분야는 컴퓨터공학 전공자들 중에서도 관심을 가지는 사람이 별로 없다. 분야 자체가 공학적 분야라기보다는 수학적 분야에 가깝고, 알고리즘이야 남이 만든 걸 가져다 쓰는 경우가 많기 때문. 다만, 상용 소프트웨어 개발에서는 [math]n^2[/math]와 [math]n^3[/math] 알고리즘의 차이는 단지 몇 초~수 분 차이일 뿐이지만 이를 사용하는 사용자 입장에서는 충분히 느낄 수 있을 정도기에 그 중요성은 매우 크다. 예를 들어, 내부 알고리즘이 느려서 버튼 하나 누를 때 마다 5초간 기다리다가 다음 작업을 하는 것과 1초 미만의 시간을 기다리고 다음 작업을 하는 것은 상당히 큰 차이가 있다. 모 게임에서는 [math]n^5[/math] 만큼의 시간복잡도를 가지는 알고리즘이 적용되어 있던 내부 모듈을 [math]n^3[/math] 만큼의 시간복잡도를 가지게 개선하여 유저들의 극 호평을 받은 적이 있다. 이미 출시되어 있는 알고리즘을 가져다 쓰면 되지 않느냐? 라고 반문하는 경우도 있지만, 개발자들에게는 택도 없는 소리인 경우가 많다. 정렬 알고리즘 같은 경우에는 갖다 써도 되는거지만, 예를 하나 들어보자. "[math]N*M*L[/math] 크기의 직육면체를 최소한의 절단 횟수로 정육면체로 나눈다고 할 때, 몇 조각이 나오겠는가?" 에 대한 알고리즘이 인터넷에 찾는다고 있을 것 같은가? ~~있긴 있다. 프로그래밍 경진대회에서 나왔던 문제니까~~ 이는 마치 P-NP 문제에 대한 개요를 가르쳐 주고, 이 증명을 인터넷에서 찾아서 가지고 오라는 말과 다를 바가 없다.
아무튼, 정작 컴퓨터에서 매우 중요한 학문인데 대우는 안습한 기초 학문 분야의 한 사례라 할 수 있겠다. 지못미

4 극미한 점근에 대한 이해

수학에서, 근사값의 오차항(error term)에 대해서 나타낼 때 중요하게 쓰인다.
알고리즘에서는 [math]N[/math]이 무한대로 갈 경우에 대해 사용했지만 수학에서는 [math]x[/math]가 [math]0[/math]으로 갈 경우에 대해 사용한다고 Small-oh Notation([math]o\left(x\right)[/math] 같은 식으로)로 표기하는 경우도 있다.

예를 들자면, [math]x[/math]가 [math]0[/math]에 가까울 때 지수함수는 다음과 같이 쓸 수 있다.
[math]e^x = 1 + x + \frac{x^2}{2!} + E[/math]

여기서 E는 Error Term인데, x가 충분히 0과 가깝다면 E는 [math]x^3[/math]에 어떤 상수를 곱한 것의 절댓값보다 작다. 즉, E를 [math]o\left(n^3\right)[/math] 로 쓸 수 있다.
자연상수를 참고하면 위의 식을 이해하는데 도움이 된다.

5 기타

하한 점근과 상/하한 점근이 있다.
각각 [math]\Omega[/math]와 [math]\Theta[/math]로 표기한다.

[math]f(x) = \Omega(g(x))[/math]
[math]\displaystyle \lim_{x\to a} \left|\frac{f(x)}{g(x)}\right| \gt 0[/math]

[math]f(x) = \Theta(g(x))[/math]
[math]0 \lt \displaystyle \lim_{x\to a} \left|\frac{f(x)}{g(x)}\right| \lt \infty[/math]

다항식으로 설명하자면 [math]\Omega[/math]는 g(x)의 최대 차수가 f(x)의 최대 차수보다 작아도 상관 없지만
[math]\Theta[/math]는 최대 차수가 엄격하게 같아야 한다.

6 참고

7 관련 항목

↑ 명령문 x=y와 x=y+z+(x/y)+(x*y*z-x/z)는 둘 다 한 단계로 계산한다.
↑ 개념의 이해만을 위해 덧붙이자면, 친구네 집 아파트(101동)에 도달했을 때, 친구네 주소(302호)를 알고 있으면 [math]O\left(1\right)[/math]로 친구네 집에 들어갈 수 있다. 그런데 101동밖에 모른다면, 최악의 경우 그 101동의 모든 동호수를 뒤져가며 찾아야지 않겠는가? 이런 경우를 [math]O\left(n\right)[/math]으로 생각할 수 있겠다.
↑ [math]3^n[/math]은 [math]\left(2^n\right)^{\lg 3}[/math]으로도 쓸 수 있기 때문에 [math]2^n[/math]의 예시만 드는 경우도 많다.
↑ 이를 대표적으로 나타내는 것이 정렬 문제이다. 이중 for문을 사용한 정렬은 시간복잡도가 [math]n^2[/math]로 sort 함수를 이용한 정렬과 비교했을때 수행시간이 엄청나게 길어지게 된다.
↑ 64배 차이가 큰 차이가 아니라는 것은 사실 이상하지만, 위 표에서 보듯 시간복잡도의 형태 자체가 달라지면 본문에 비슷하게 서술한대로 안드로메다급 차이가 나기 때문에, 비교적 차이가 매우 적게 난다는 뜻. [math]n[/math]의 값이 커지면 커질수록 이 차이는 물론 더욱 급격하게 벌어진다.
↑ 압축 암호찾기 프로그램의 경우, 정해진 글자에 따라 모든 경우를 하나하나 대입하므로 [math]n [/math]값이 조금만 커져도 수행시간이 넘사벽으로 나타나는 것을 알 수 있다. 영문자 소문자(26)+대문자(26)+숫자(10)+공백 정도만 해도 총 시간복잡도가 [math]O\left(63^n\right) = O\left(2^{n\log63}\right)[/math]의 형태이기 때문에, [math]n = 6[/math] 만 되어도 약 625억 사이클의 연산이 필요하다. 즉, 조금만 긴 암호에 대해서는 전혀 쓸모없는 프로그램이다.
↑ 초당 10억 개의 명령문을 수행하는 컴퓨터가 [math]n=1000[/math]이고 [math]2^n[/math]의 작업을 수행한다면 [math]3.4\times 10^{284}[/math]년(약 3 나유타 아가라 년) 동안의 시간이 필요한데, 이정도면 우주가 통째로 멸망하고도 남는다. 참고로 1아가라는 [math]10^{224}[/math].

[1] 명령문 x=y와 x=y+z+(x/y)+(x*y*z-x/z)는 둘 다 한 단계로 계산한다.

[2] 개념의 이해만을 위해 덧붙이자면, 친구네 집 아파트(101동)에 도달했을 때, 친구네 주소(302호)를 알고 있으면 [math]O\left(1\right)[/math]로 친구네 집에 들어갈 수 있다. 그런데 101동밖에 모른다면, 최악의 경우 그 101동의 모든 동호수를 뒤져가며 찾아야지 않겠는가? 이런 경우를 [math]O\left(n\right)[/math]으로 생각할 수 있겠다.

[3] [math]3^n[/math]은 [math]\left(2^n\right)^{\lg 3}[/math]으로도 쓸 수 있기 때문에 [math]2^n[/math]의 예시만 드는 경우도 많다.

[4] 이를 대표적으로 나타내는 것이 정렬 문제이다. 이중 for문을 사용한 정렬은 시간복잡도가 [math]n^2[/math]로 sort 함수를 이용한 정렬과 비교했을때 수행시간이 엄청나게 길어지게 된다.

[5] 64배 차이가 큰 차이가 아니라는 것은 사실 이상하지만, 위 표에서 보듯 시간복잡도의 형태 자체가 달라지면 본문에 비슷하게 서술한대로 안드로메다급 차이가 나기 때문에, 비교적 차이가 매우 적게 난다는 뜻. [math]n[/math]의 값이 커지면 커질수록 이 차이는 물론 더욱 급격하게 벌어진다.

[6] 압축 암호찾기 프로그램의 경우, 정해진 글자에 따라 모든 경우를 하나하나 대입하므로 [math]n [/math]값이 조금만 커져도 수행시간이 넘사벽으로 나타나는 것을 알 수 있다. 영문자 소문자(26)+대문자(26)+숫자(10)+공백 정도만 해도 총 시간복잡도가 [math]O\left(63^n\right) = O\left(2^{n\log63}\right)[/math]의 형태이기 때문에, [math]n = 6[/math] 만 되어도 약 625억 사이클의 연산이 필요하다. 즉, 조금만 긴 암호에 대해서는 전혀 쓸모없는 프로그램이다.

[7] 초당 10억 개의 명령문을 수행하는 컴퓨터가 [math]n=1000[/math]이고 [math]2^n[/math]의 작업을 수행한다면 [math]3.4\times 10^{284}[/math]년(약 3 나유타 아가라 년) 동안의 시간이 필요한데, 이정도면 우주가 통째로 멸망하고도 남는다. 참고로 1아가라는 [math]10^{224}[/math].

[1]

[2]

[3]

[4]

[5]

[6]

[7]