복잡도와 점근표기법(빅오표기법)

본래 점근표기법은 수학적 개념으로, 임의의 함수에 대하여 정의역의 원소가 커짐에 따라 그 원소의 상이 얼마나 빠르게 커지는지를 표현하는 것이다. 그러나 컴퓨터의 경우, 1의 연산과 100, 1000의 연산에 거의 차이가 없다. 이 말은, 컴퓨터가 연산하는 과정을 1의 단위까지 세세하게 고려하더라도 명확한 성능 차이를 드러내지는 않는다는 것이며, 따라서 프로그래밍 과정에서 점근표기법을 통해 프로그램 알고리즘의 복잡도을 표현하는 것은 근사값에 대한 정의를 나타내는 것이다.

 

즉, 프로그램에 있어서 점근표기법이란, 한 프로그램이 실행되는 과정에 소요되는 시간(단계)를 나타내며, 그 과정에서 계수와 상수를 제거한다. 이는 컴퓨터의 연산속도가 사람과 다르기 때문에 계수와 상수로 이뤄지는 횟수의 차가 실제 차이만큼 두드러지지 않기 때문이다. 즉, n이라는 단계횟수가 있다면 n의 1승에 가까운지, n의 n승에 가까운지에 대한 비례를 고려하는것이 프로그램 알고리즘 성능을 나타내는데 더욱 명확하다는 뜻이다.

 

간단한 예를 들면 T(n) = 4n + 8이라는 수식의 경우, 점근표기를 활용하게 되면 O(n)이 된다. 이는 O(T(n))에 있어서 계수와 상수를 모두 제거하기 때문이다. 그러나 이것이 무척 커져서 n의 2승에 가까운 크기가되면 O(n^2)가 된다. 

이렇게 보면 점근표기법은 사실상 '상한'의 개념이다. 즉, 어떤 프로그램의 단계 횟수에 있어서 근사치까지 도달하는 과정에 대한 수치기 때문에 저 값을 넘어가게 되면 O(n^3)에 가까워 지는 것이 되기 때문이다.

 

시간 복잡도 : 실행에 필요한 시간을 평가한 것

공간 복잡도 : 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것

 

복잡도에는 공간복잡도와 시간복잡도가 있는데, 최근에는 공간복잡도보다 시간복잡도를 중요하게 여긴다. 그 이유는 하드웨어 성능의 발달로 메모리 공간에 대한 효율적인 이용이 과거에 비해 상대적으로 줄어들어(중요하지 않다는 게 아니다) 공간복잡도보다는 시간복잡도의 개선에 더 중점을 두기 때문이다. 

 

 

시간 복잡도와 로직의 수행 시간은 비례하므로, 시간 복잡도 수치가 작을수록 효율적인 알고리즘이라고 볼 수 있다.

 

예를 들어 n에 대한 O(1), O(log n), O(n), O(nlogn), O(n^2), O(n^3), O(2^n), O(n!)을 표로 비교해보면

시간/n	1	2	3	4	8	16	32	64	1000
1	1	1	1	1	1	1	1	1	1
log n	0	1	1.58	2	3	4	5	6	9.97
n	1	2	3	4	8	16	32	64	1000
n log n	0	2	4.75	8	24	64	120	384	9966
n^2	1	4	9	16	64	256	1024	4096	1000000
n^3	1	8	27	64	512	4096	32768	262144	1000000000
2n	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이 값이 커지면 커질수록, 아래로 올 수록 수행시간이 급격히 길어지게 된다. 따라서 시간복잡도의 차수가 하나 낮아진다는건 어마어마한 성능의 향상을 의미하는 것이기도 하다. 

 

다음에는 선형검색과 이진검색을 통해 실제 시간 복잡도를 따지는 과정에 대해 알아보고자 한다.