무한수열이란?

알고리즘은 무한대의 숫자를 상대로 연산을 수행하므로 수학에서 정의하는 무한수열의 성질을 잘 이해하고 있어야만 한다. 무한수열은 기호로 표현하면 lim(n→∞)로 나타낼 수 있으며 무한대 값을 n을 통해 정의하는 형태라 할 수 있다.

우선 무한수열을 이해하기 위해서는 수학에서 제공하는 2가지 주요한 개념을 이해해야만 하는데 그것은 바로 수렴과 발산이다. 보통 무한의 개념에 익숙치 않은 사람들은 무한대의 값이 범위가 없는 어마어마한 수의 집합이라고 생각할 수도 있겠지만 엄밀히 말하자면 무한의 값에도 엄영한 범위가 존재한다. 예를 들어 1과 2사이는 정수의 범위에서 어떠한 수도 존재할 수 없지만 실수의 범위에서는 셀 수 없이 많은 무한대의 수가 존재하게 된다. 프로그래밍에서는 당연히 실수의 범위를 허용하고 있으므로 우리는 이러한 수의 무한개념을 최대한 근사값을 통하여 표현할 수 있게 된다.

우선 수렴에 대한 수학적인 표현은 다음과 같다.

lim(n→∞) An = α

이 뜻은 무한대의 값 n이 A에 수렴하고 있다는 뜻인데 쉽게 말해 n이 끝없이 A에 가까워지고 있다는 뜻이다. 무한수열에서 수렴은 A에 끝없이 가까워지긴 하지만 절대로 A가 되지는 않는다. 다만 n이 시작하는 지점에서 A에 가까워지 구간 사이에 모든 수의 배열을 의미한다.

발산은 이와 반대인데 

lim(n→∞) An = ∞ 또는 lim(n→∞) An = -∞

위와 같이 표현하고 있다. 우측은 음의 발산이고 좌측은 양의 발산을 의미하며 각각 양의 무한대와 음의 무한대를 표현하고 있다. 여기서 정석의 내용을 다룰 것은 아니므로 더 많은 무한의 개념에 대해서는 각자 공부하기로 하고 다음으로 넘어가자.

우리가 알고리즘을 공부하는 까닭은 무엇보다도 좋은 알고리즘을 구현하기 위해서라 할 수 있다. 알고리즘은 사람의 눈에 보이는 물질적인 존재가 아니므로 좋은 알고리즘을 어떠한 외형이나 골격을 통해 규정할 수는 없는데다 마냥 좋은 알고리즘이라고 하기에는 그 범위가 너무 크므로 우리는 어떠한 기준을 통해 좋은 알고리즘을 선별해야만 한다. 물론 프로그래밍 적으로는 OOP, SRP, OCP와 같은 원칙들로 좋은 알고리즘을 선별할 수도 있겠지만 이러한 원칙은 불변하는 원칙이 아니므로 기준으로 삼기에는 무리가 있다.

그렇다면 이러한 원칙들이 있기 이전부터 존재하면서 아직까지도 통용되고 있는 불변의 알고리즘 기준은 무엇일까? 잘 정리된 알고리즘? 짧은 알고리즘? 이러한 기준들도 주요하겠지만 무엇보다도 변하지 않는 가치를 지닌 기준은 바로 속도일 것이다. 동일한 연산을 더욱 빠르게 수행할 수 있는 알고리즘은 누가 보더라도 좋은 알고리즘이며 불필요한 리소스를 낭비하지 않으므로 최적화되어있다고도 할 수 있다. 잘 정리되고 짧은 알고리즘이라 하여 불필요한 리소스가 낭비되지 않는다는 보장은 없으므로 이러한 원칙은 유한자원 체제에서 기준으로 인정받을 수는 없는 노릇이다.

대신 속도만큼은 이런 유한한 자원을 효율적으로 사용할 수 있게 해주는 산업적 의미가 큰 기준이므로 현대의 모든 알고리즘은 바로 이 속도에 근간하여 발전해왔다. 그러므로 알고리즘을 공부한다는 것은 동일한 연산을 더욱 빠르게 처리할 수 있는 방법을 공부하는 것이며 자신의 알고리즘의 처리속도가 어느 정도인지 예측하는 기준을 공부하는 학문이라 할 수 있겠다.

알고리즘에는 다음과 같이 속도를 표기하는 표기법들이 존재한다.

우선적으로 표기법을 살펴보기 전에 알고리즘에서 어떤 방식으로 속도를 표현하는지 살펴보도록 하자. 알고리즘에서 수행시간은 연산횟수와 비례한다 할 수 있다. 연산횟수가 증가한다면 수행시간도 함께 증가할 것이며 반대로 연산횟수가 감소하면 수행시간도 함께 감소한다. 그러므로 우리는 해당 알고리즘은 총 몇번의 연산횟수를 가지고 있는지 알 수만 있다면 수행속도도 함께 측정가능한 셈이다.

반면에 연산속도는 하드웨어 성능과 밀접한 관계를 맺고 있으므로 기준치를 잡기가 굉장히 모호하다. 동일한 알고리즘이라도 다른 하드웨어 구성에서 커다란 속도의 차이가 생길 수 있으며 이러한 오차를 인정하기엔 그 범위가 너무 크다. 그러므로 우리는 속도의 측정값으로 시간값보단 횟수에 의존하는 것이 더욱 객관적이라 할 수 있을 것이며 실제로 알고리즘의 수행속도를 측정할 때 바로 이 수행횟수를 기준으로 삼고 있다.

다음의 코드를 살펴보자.

int n=임의의 수;

for(int i=0; i<n; i++) n+=n;

위와 같은 코드가 실행될 경우 우리는 해당 알고리즘이 n번만큼 연산이 반복된다는 사실을 알 수 있다. 즉 연산횟수는 n이며 표기법으로 표현하자면 이를 O(n)과 같이 표현할 수 있다. 두번째 예제를 보자.

int n=임의의 수;

for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
j+=i+n;
}
}

위의 코드에서는 n번의 연산이 n번만큼 반복되므로 n의 제곱만큼의 연산횟수가 발생한다. 이를 표기법으로 표현하자면 O(n^2)과 같이 표현할 수 있으며 for문을 2개 썼을 뿐이지만 제곱의 리소스를 더 사용하게 된 셈이다. 물론 이런 상황이 꼭 리소스의 낭비라 할 수는 없겠지만 무엇보다도 소스가 짧고 간결하게 표현됬다고 해서 좋은 알고리즘이라 할 수는 없다는 결론정도는 얻은 셈이다.

결론적으로 Ο-표기법은 위와 같이 연산횟수에 대한 표기법이며 구체적인 연산횟수보다는 대략적인 값을 상한으로 추정해 알고리즘의 속도를 표현하게 된다. 그리고 중요한 것은 알고리즘 속도표기법은 항상 연산식의 최고차항, 즉 가장 큰 수를 기준으로 정하게 되는데 그 이유는 알고리즘에서 최고차항을 제외한 상수의 속도는 측정값에 별다른 영향을 끼치기 못하기 때문이다.

예를 들어 해당 연산이 '5n^2 + 3n'의 속도로 연산된다면 표기법은 최고차항의 나머지는 무시하고 오로지 최고차항의 상수를 제외한 값만 받아들인다. 그러므로 '5n^2 + 3n'을 표기법을 사용해 표현하면 Ο(n^2)과 같다. 

아직 이해가 덜된 독자가 있을 수도 있으므로 표기법에 대해 좀 더 이야기 해보도록 하자. 예를 들어서 다음과 같은 연산이 존재할 때 표기법은 다음과 같이 표현해낼 수 있다.

int n=임의의 수

for(int i=0; i<n; n++ { … }
for(int i=0; i<n; n++ { … }

위의 예제에서는 for문을 2번 사용하긴 했지만 n번 연산이 그냥 2번 발생하는 것 뿐이므로 총 2n만큼 속도가 발생한다. 이를 표기법으로 표현해보면 항상 상수를 제외한 최고차항의 값만을 표기하므로 연산속도는 O(n)과 같다. 굉장히 쉽지 않은가? 아마 이쯤되면 읽는 이들도 표기법 표현에 대해 약간은 감이 올 수도 있을 것이다.

그렇다면 좀 더 구체적으로 생각해보자. O-표기법은 대개 상수를 사용하기 보단 n과 같은 임의의 수를 이용해 표현하곤 한다. 그 까닭은 대입되는 수가 항상 일정치 못하고 임의의 값일 경우가 많은 이유 때문이었는데 활용도 측면에 있어서도 너무 정확한 상수 데이터보다는 n과 같은 임의의 값을 통한 측정이 여러모로 더 유용하다는 이유도 있다. 여하튼 전산학자들은 이런 임의의 수 n을 기준으로 알고리즘의 속도값을 매번 측정하다보니 본의 아니게 매우 자주, 그리고 동일하게 나오는 몇가지 값들이 존재함을 깨닫게 되었으며 점차 이런 값들은 서로간의 알고리즘 속도를 비교하는 기준으로 통하게 되었다.

예를 들어 다음의 값들은 모두 O(n)의 범주에 속한다.

int n=임의의 수

① for(int i=0; i<n; i++){ … }

② for(int i=0; i<n; i++){ … } for(int i=0; i<n; i++){ … }

③ 100n

④for(int i=0; i<n/2; i++){ … } 

… 

이렇게 보면 O(n)에는 꽤나 상상을 초월하는 어마어마한 알고리즘들 속도의 범주가 포함되고 있다는 사실을 알 수 있을 것이다. 그리고 이런 다양한 범주의 집합을 가진 임의의 수 중이 빈번히 사용되는 것들을 꼽고 그걸 속도 순으로 정리해보자면 아래와 같다.

n^2 > n log n > n > log n

로그는 지수를 표현하는 방법인데 잘 모르는 사람을 위해 짧막하게 설명하자면 지수는 값이 증가함에 따라 본래의 값이 어마어마하게 비대해지다는 성격을 가지고 있다. 그렇다면 반대로 본래의 어마어마한 값이 있더라도 이를 지수로 표현하면 매우 적은 수가 나오게 된다고 생각할 수 있지 않을까?

n log n은 log n^2와 같으므로 n=1일 때 0, n=2일 때 2, n=3일 때 4,75, n=4일 때 8, n=5일 때 11… 등등 O(n)보다는 느리지만 n^2보다는 낮은 속도를 가진 표현이다.

이렇게 빅오표기법을 이용해 속도를 계산하는 방법에 대한 설명을 모두 끝나쳤다. 사실 여기다 재귀호출 알고리즘의 계산까지 넣으려 했었지만 내용이 너무 길어지는 듯 하여 여기까지 마무리하고자 다음 문서에서 자세히 설명토록 하겠다. 마지막으로 O표기법 외의 다양한 표기들을 간략하게 설명하고 마친다.

Ο-표기법

이 표기법은 해당 속도가 알고리즘의 연산횟수를 포함하고 있을 때 사용한다. 즉 Ο(n^2)는 최고차항이 n^2보다 작은 모든 연산횟수를 포함하며 해당 연산이 아무리 심해져도 해당 표기법을 능가하지 않는다는 것을 표현한다.

Ω-표기법

이는 Ο-표기법과 반대인 하한적 표현이다. 해당 연산횟수는 최소한으로 발생할 수 있는 속도를 의미한다.

Θ-표기법
위 두 표기법의 교집합을 나타낸다. 상한과 하한의 값을 동시에 내포하고 있으나 최고차항의 연산횟수를 벗어나지는 못한다.