Algorythms Big-O (or Big-oh) notation

Big-O (or Big-oh) notation

계산 복잡도 이론에서 사용되는 점근 표기법. 입력 데이터의 크기와 알고리즘의 소요 시간 또는 메모리의 상관관계를 나타낸다.

1.1. 정의

모든 n(n은 어떤 n0보다 크거나 같다)에 대해 |f(n)|=<c|g(n)|인 조건을 만족하는 두 양의 상수 c와 n0가 존재한다면 f(n) 은 o(g(n))에 속하게 된다.

1.2. 설명

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

결국 정의와 연관시켜서 생각하면 O(5n+7) = O(5n) = O(n)이 되고, O(n²+25)=O(n²)이 된다는 뜻이다. 여기서 = 기호를 '같다(equals)'가 아니라 '~이다(is)', '~쯤 된다'라고 해석하면 기호의 혼란을 피할 수 있다. 경우에 따라 O(g(n))을 하나의 집합으로 보고 f(n) ∈ O(g(n))으로 표기하기도 한다. 일반적으로 알고리즘의 시간복잡도를 나타내는데, Big-O 표기법은 해당 알고리즘의 시간 복잡도 중 해당 차수의 시간복잡도를 알고리즘이 가지거나, 혹은 그 보다 더 낮은 차수의 시간복잡도의 알고리즘을 가진다는 이야기인데.. 쉽게 풀어 설명하면, 알고리즘의 성능을 결정하는 시간복잡도는 아래 순이다. (위로 갈수록 간단하고, 아래로 갈수록 복잡해지며, log N은 log₂N을 뜻한다)

- O(1) 과 같은 상수형태
- O(log n) 과 같은 로그 형태
- O(n) 과 같은 선형[2]
- O(n log n) 과 같은 선형로그 형태
- O(n²), O(n³)과 같은 다차 형태
- O(2ⁿ), O(3ⁿ)과 같은 지수 형태[3]
- O(n!) 과 같은 팩토리얼

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

예를 들어, O(log n), O(n), o(n log n), o(n²), o(n³), o(2ⁿ), o(n!)를 비교하면,

n	1	2	3	4	8	16	32	64	1000
log n	0	1	1.73	2	3	4	5	6	9.97
n	1	2	3	4	8	16	32	64	1000
n log n	0	2	5.19	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	10억
2ⁿ	2	4	8	16	256	65536	4294967296	약 1844경	약 1.07 x 10^301
n!	1	2	6	24	40320	20922789888000	약 2.63 x 10^35	약 1.27 x 10^89	약 4.02 x 10^2567

 

n의 값이 적을 때는 알고리즘 사이 큰 차이가 없고, 심지어 시간복잡도가 복잡한 알고리즘이 시간복잡도가 낮은 알고리즘보다 부분적으로 빠른 경우도 있지만, 보다시피 n이 값이 커지면 커질수록, 시간복잡도가 복잡한 알고리즘은 수행시간이 급격하게 길어지게 된다. 비슷한 형태의 시간복잡도를 가진 함수는 사실 큰 차이가 없지만, 시간복잡도 함수의 형태 자체가 다르면 바로 신세계가 열리는 것을 볼 수 있다. n=64일 때, n²와 n³은 64배 차이가 나지만[4], n²와 2ⁿ의 차이는 어마어마한 것을 보라.[5] 이로 인해서인지, 매우 작은 수의 n 값만이 입력값으로 들어오는 몇몇 특별한 알고리즘이 아닌 이상, 지수급 이상의 시간복잡도를 가지는 알고리즘은 어느 정도 큰 n 값이 입력으로 들어올 때 성능이 급격하게 떨어지므로, 지양이 되게 된다. 특히 팩토리얼 값 이상이 되면 거의 써먹을 수가 없다. 스털링 근사를 이용하면 n!≒(n/e)n이므로 억지로 만든다면야 팩토리얼 이상의 O(n^n^....n) 형태 (n^n, n^n^n, n^n^n^n.. 식으로 증가)의 시간복잡도를 가진 루프를 만즐 수도 있지만, 일반적으로 알고리즘을 다룰 때에는 전수조사보다 효율적인 것만 다루는데, 대개의 경우 전수조사가 O(n!)이라 nn 같은 것은 다루지 않는다.[6] 이것을 또 뒤집어 말하면, 알고리즘을 어떻게든 연구해서 개선해서, 예를 들어 2n 과 같은 지수형태의 알고리즘의 코드를 개선해 nx 형태로만 어떻게 개선한다면 알고리즘의 엄청난 성능 향상을 기대할 수 있다는 말. 이런 고로, 프로그래밍 등에서 보통 알고리즘 과목은 전공필수 내지 공학인증필수 과목으로 지정되고 있다. 그만큼 중요하고, 알아 두면 쓸 곳이 많기 때문. 배우는 사람에게는 전혀 와닿지 않는 말이지만 말이지 하지만 정작 이쪽 분야는 컴퓨터공학 전공자들 중에서도 관심을 가지는 사람이 별로 없다. 분야 자체가 공학적 분야라기보다는 수학적 분야에 가깝고, 알고리즘이야 남이 만든 걸 가져다 쓰는 경우가 많기 때문. 상용 소프트 개발에는 그리 도움이 되지도 않고, 하드웨어의 발달로 O(n!)같은 게 아니라면 일단 어느 정도 써먹을 수 있게 되었고, 제아무리 파 봐도 나오는 결과는 굉장히 미미한지라 필요성을 체감하기 어렵다. 그래도 더 나은 알고리즘을 만들기 위한 학문보다는 O(2n)이나 O(n!) 같은 병맛 알고리즘들을 피해가는 정도의 지식을 얻는 것으로는 나름 큰 의미가 있다. 아무튼, 정작 컴퓨터에서 매우 중요한 학문인데 대우는 안습한 기초 학문 분야의 한 사례라 할 수 있겠다.

<출처 :엔하위키미러>