좋은 알고리즘이란? / 빅오표기법

위의 문서를 읽었다면 빅오표기법에 대해서는 어느 정도 알고 있을테고 혹시나 빅오 표기법에 대해 잘 모르고 있다면 지금이라도 링크된 문서를 읽은 뒤에 현재의 문서를 읽는 것이 바람직 하다. 아무래도 이 포스트는 전산학과 개강 타임에나 인기가 있을 법한 글이 될 것 같지만 뭐 어찌됬던 지식을 공유하는 것은 바람직한 현상이므로 혹시나 설명에 모자란 부분이 있다거나 해당 학교 교수님이 덜 설명해준 부분이 있다면 언제든지 댓글로 질문해주길 바란다. 만약 쉽게 배우는 알고리즘이란 교재를 통해 공부하고 있다면 51쪽 점화식의 이해을 참고하며 이 문서를 읽는 것이 좋다.

점화식이란 자기자신을 호출을 하는 알고리즘, 즉 계승의 성격을 가진 알고리즘을 분석하여 식으로 표현하는 방법이다. 우리는 이전의 문서에서 빅오표기법을 이용해 간단하게나마 알고리즘의 수행시간을 측정하는 방법을 알아봤는데 잠깐 복습하는 타임으로 다음의 예제를 살펴보자.

viewMemberInfo (A[], n)
{
for i ← 1 to n
for j ← 1 to n
print(A[i], A[j])
}

print (p, q)
{
p와 q를 출력한다.
}

위와 같은 알고리즘의 연산시간을 우리는 빅오표기법을 사용하여 다음과 같이 표현할 수 있다는 사실을 지난 문서에서 공부하였다. 자기 자신이 호출되지 않는 알고리즘은 무한수열이 갖고 있는 독특한 성질을 이용하여 최고계수의 값만 구하면 모두 해결되므로 위의 알고리즘의 시간을 아래와 같이 표현할 수 있다.

위와 같이 재귀의 성질을 갖지 않는 알고리즘의 속도는 매우 쉽게 측정할 수 있으며 별도의 연산과정이 불필요할 정도로 간단명료하다. 그렇다면 재귀의 성질을 갖는 알고리즘의 계산은 과연 어떠할까?

우선 재귀의 성질을 갖는 알고리즘을 하나 만들어보자. 초장부터 김빠지게 장난질하기보단 보다 빠른 이해를 위해 간단하게 팩토리얼 알고리즘 정도가 딱 좋겠다.

위의 팩토리얼 알고리즘의 속도를 일단 대략적으로 한번 계산해보자. 우선 해당 알고리즘의 시작되면 인자 값에 계속해서 -1을 더하는 자기자신의 알고리즘이 수행되다가 n이 1이 되는 순간 모든 연산이 종료된다. 즉 이를 가장 단순한 수학적 표현으로 바꿔본다면 1 + 2 + … + (n-3) + (n-2) + (n-1) 로 표현해낼 수 있을 것이다.

그렇다면 팩토리얼 알고리즘은 총 몇번의 연산이 수행되는가? 조금만 머리를 써본다면 재빨리 n번의 연산이 반복된다는 사실을 알 수 있을 것이다. 왜냐하면 위의 연산은 자기 자신이 1이 될 때까지 연산을 반복하기 때문이다. 그리고 우리가 미리 배워둔 점근적 표기를 이용한다면 위의 알고리즘은 O(n)의 복잡도를 가지고 있다고 할 수 있다.

아마 재귀 알고리즘 계산들이 모두 위와 같기만 하다면 재귀호출이라고 해서 유별나게 속도 측정이 어려울 것 같지만은 않다. 헌데 위의 예제는 정말 재귀호출 중에 가장 쉬운 문제 중에 하나일 뿐 사실 재귀호출의 속도 측정은 그렇게 쉬운 일이 아니다. 왜냐하면 재귀호출을 할 때에 위처럼 자기 자신에서 -1만 더하는 알고리즘만 있는게 아니라 나눗셈 연산을 하는 알고리즘도 있고 -1000을 더하거나 -100을 더하고 별의 별짓을 다하는 재귀 알고리즘들이 존재하기 때문이다.

이러한 복잡한 구성을 가진 재귀 알고리즘들은 속도 측정하기가 매우 까다로우므로 다른 알고리즘처럼 암산만으로 해결할 수가 없다. (물론 재귀 알고리즘을 간편하게 계산하는 마스터 정리를 이용한다면 암산으로도 가능하지만…) 오늘 우리는 이런 재귀 알고리즘을 계산하는 3가지 점근적 복잡도 계산법을 알아볼 것이며 직접 활용해 계산까지 해보는 과정을 거쳐볼 것이다.

반복대치는 위의 팩토리얼을 계산했던 것처럼 1 + 2 + … + (n-3) + (n-2) + (n-1)와 같은 연산이 반복적으로 이루어졌다는 가정 하에 점근적 복잡도를 구하는 방식이다. 반복대치는 재귀 알고리즘의 속도를 구할 수 있는 가장 바람직한 방법이므로 눈으로만 읽지 말고 반드시 이해하고 깨우치도록 하자. 그리고 이제부터는 암산이 아니라 직접 검증을 통한 방식으로 점근적 복잡도를 구할 것이므로 아래와 같은 재귀 알고리즘 표현식에도 익숙해져야만 한다.

위 계산식은 팩토리얼 알고리즘을 수학적으로 표현한 것이다. 좌측 대입부분의 T(n)은 팩토리얼 알고리즘을 구하는데 총 소요되는 시간을 뜻하며 우측 연산식에서 T(n-1)은 재귀가 호출되는 시간, c는 재귀가 호출되는 것 이외에 소요되는 오버헤드 시간이다. 위와 같이 재귀 알고리즘을 수학적으로 계산하기 위해 3가지 형태로 나누는 것은 매우 기본적인 사항이므로 반드시 이해가 될 때까지 반복해서 학습해야만 한다.

이제 어느 정도 이해가 갔다면 반복대치를 이용해 해당 식을 계산해보자.

만약 반복대치를 처음 접하는 경우라면 이 연산과정 때문에 상당히 머리 속이 복잡해질 수도 있겠다. 사실 이건 반복연산 중에서도 가장 쉬운 편에 속하지만 알고리즘이란게 본디 무한수열의 속성을 띈 연산이기 때문에 가급적 사칙연산의 간단한 수학적 개념은 버리고 오로지 무한의 개념으로 해당 식을 이해해야만 정신건강에 이롭다.

우선 수학적인 연산은 둘째치고 프로그래밍 코드로 이해한다는 마음으로 해당 식을 바라보자. 준비됬는가? 자! 팩토리얼의 총 소요시간 T(n)에 대해서 알고리즘 상 지속적으로 반복된다고 할 수 있는 부분은 과연 어느 어디일까? 그렇다. 알다시피 바로 재귀부인 T(n-1)이 될 것이다. 그렇다면 T(n-1)이 반복됨으로 인해 계속해서 누적될 수 밖에 없는 부분은 과연 어디일까? 그렇다. 재귀부를 제외한 오버헤드 부분은 재귀부가 실행될 때마다 누적되는 부분이다.

그렇다면 이것을 수학적으로 표현하여 검증한다면 바로 위와같은 식을 구성할 수 있다. 딱 5번째줄까지 말이다. 그 아래는 아직 쳐다보지도 말고 5번째 줄까지만 봐라.

T(n-1)+c가 실행됨과 동시에 재귀부가 재호출되어 T(n-2)가 되었다. 재귀가 호출됨에 따라 자동적으로 오버헤드가 하나 쌓이게므로 c를 하나 더해주어 2c를 만들어준다. 세번째줄 연산도 마찬가지다. T(n-2)가 실행됬으므로 재귀부는 T(n-3)이 되고 오버헤드가 하나 더 쌓여 3c가 되었다. 그리고 알고리즘은 이런 식으로 계속해서 재귀부가 호출됨에 따라 오버헤드가 쌓이는 형태로 n이 1이 될때까지 연산반복될 것이다.

그렇다면 마지막까지 가서는 알고리즘이 어떻게 될까? 아마 최종적으로 T(1)이 호출되면 if(n==1) return 1 조건을 충족하게 되므로 이 때는 기존과 다르게 벼롣의 오버헤드가 발생하지 않고 모든 알고리즘이 종료하게 될 것이다. 그러므로 T(n)번부터 시작하여 T(1)까지 실행되었다고 가정했을 때, 오버헤드는 총 (n-1)번 만큼 쌓이게 된다고 할 수 있으며 이를 수학적으로 표현하자면 5번째 줄처럼 나타낼 수 있게 된다.

그렇다면 6번째줄은 도대체 뭘까? 정말 뜬금 없어도 너무 뜬금이 없다. T(1)+(n-1)c = cn이라니… 누구를 바보로 아는건가!? 라고 교수에게 따졌다간 재적당하기 쉽상이다. 마음을 가다듬고 다음의 설명을 보도록 하자. 수학은 치환을 통해 식을 최대한 줄여 가능하다면 한글자로까지 표현하는 것을 너무너무 좋아하므로 위와 같은 수학적 표현도 다른 변수로 치환될 수 있다면 최대한 치환하여 줄이는 형태로 바꿔야 될 것이다.

이전에도 말했다시피 알고리즘은 무한수열의 개념을 사용하는 학문이므로 위의 식에서 = 는 사실 ∈와 비슷한 의미로 해석할 수가 있다. (물론 깊게 들어간다면 엄연히 다르긴 하지만 우리가 뭐 수학자도 아니니까…) 이는 수학적으로도 용인하는 표현법인데 간단한 예를 들어 아래와 같은 수식을 이해하도록 해보자.

이 수식은 수1에서 나오는 개념으로 무한의 상태를 가진 n이 끝없이 0을 수렴한다는 뜻이다. 1/n^2는 n의 값이 증가할 수록 끝없이 0에 가까워지게 되는데 물론 영원히 0이 될 수 없는 없지만 정말 너무나도 간절히…, 매일 심장을 따먹히는 프로메테우스처럼 무서우리만치 0이 되기를 소망하는 식이다.

그러므로 점화식도 위와같이 무한수열의 개념 하에 움직이는 식이므로 T(1)+(n-1)c도 무한수열의 수렴 관점에서 충분히 다른 값으로 치환될 수 있다. 알고리즘의 점근식 표기란 이전에도 말했듯이 하한과 상한의 표현만을 하고 있을 뿐 그닥 완전히 일치하는 값만 치환할 것을 요구하진 않으므로 우리는 T(1)≤c라는 수식을 통해 기존의 다루기 까다로웠던 T(1)+(n-1)c 식을 치환할 수가 있다.

우선 T(1)≤c이 어떻게 성립되는지부터 따져보자. 우리가 다른 건 몰라도 n=1일 때만큼만은 어떠한 연산이 수행될지 정확하게 집어낼 수 있으므로 T(1)이 최소한 오버헤드만큼의 연산이 수행되거나 혹은 그보다 작은 수준의 연산이 수행된다는 사실을 알고 있다. 점화식에선 암묵적으로 우측의 식 또는 좌측의 식이 다른 한쪽과 같거나 포함할 때(≤) 그냥 같다라고 표현할 수 있는 매우 유연한 가정이 통하므로 우리는 T(1)=c라는 결론을 도출해 낼 수 있다. 이런 계산법이 약간 어거지 같은가? 어차피 점근적 복잡도도 상한과 하한의 구분일 뿐 딱부러지게 '이 알고리즘은 43243번 수행됩니다~' 라는 계산을 얻는게 아니므로 이 정도의 오차는 충분히 허용된다. 그렇다고 무조건 작다고 다 치환되는 건 아니고 ≤ 정도의 같을 수도 있다는 가정이 있어야 '요건 같을 수도 있어용~' 이라면서 누가 보기 전에 빨리 빨리 해치워버릴 수 있는거다.

이제 암묵적인 합의가 오갔으므로 빨리 해당 식을 치환해서 계산을 마무리해보자. 우리가 황당해 했었던 5번째 식을 암묵적 합의를 통해 치환해보면 c+(n-1)c가 될 것이고 이것은 또 c+cn-c가 된다. 최종적으로 정리해보면 정말 깔끔하게 cn으로 값이 딱 떨어지게 된다.

그러나 여기서 만족할 일이 아니다. 숫자 주제에 감히 인간님을 괴롭게한 죄로 cn에 남아있는 한알의 강냉이까지 모조리 털어버리자. 논리는 간단한데 우리는 이전 문서에서 빅오표기법은 상수를 무시한 최고차항의 값만을 인정한다고 했었으므로 우리는 여기서 c라는 상수를 빅오표기법에서 무시할 수 있다. 그러므로 이러한 모든 과정을 거쳐 최종적으로 우리가 얻을 수 있는 값은 T(n) = cn =O(n)이 되겠으며, 팩토리얼 알고리즘은 O(n)의 복잡도를 가지고 있다 표현할 수 있다.

어떠한가? 별다른 수학적 지식이 없이도 한줄씩 한줄씩 해석하니 그닥 어렵지는 않았을 것이다. 이 기세를 몰아 조금 더 복잡한 식을 계산해보도록 하자.

위의 문제는 필자가 만들어 낸 것은 아니고 쉽게 배우는 알고리즘에서 2장 연습문제 8번을 가져온 것이다. 해당 식을 점화식으로 바꿔보면 아래와 같이 표현해낼 수 있다.

일부러 2가지 식으로 표현해봤는데 우측의 세타n은 좌측의 n을 점근적인 표현으로 바꾼 것으로 알고리즘을 계산할 때 통용되는 방식 중에 하나이다. 이러한 표현법에 대해 쉽게 배우는 알고리즘의 내용을 인용하자면

O(n)은 집합으로서의 O(n)을 의미하지 않고 O(n)에 속하는 함수 하나를 대신하는 관행적 표현이다. 이 경우에는 n을 대신한다. 식을 굳이 자세히 기술할 필요가 없는 경우에는 이런 점근적 표현을 쓰면 편리하다.

- 쉽게 배우는 알고리즘

라고 기술되어 있다. 필자는 이게 어떠한 차이가 있는지는 모르겠으나 여하튼 저런 식으로도 표현가능하다는 것을 보여주고 싶었다. 계속해서 점화식을 반복대치를 통해 빅오표기법으로 바꾸어보자.

상당히 어려졌긴 하지만 겁먹지 말고 차근차근 알아나가다보면 쉽게 이해할 수 있다. 우선 두번째 열을 살펴보면 자기 자신을 분자로 하는 재귀 알고리즘을 볼 수 있는데 이러한 나눗셈 연산이 수행되는 재귀 알고리즘은 다른 재귀호출에서는 볼 수 없는 분할의 성질이 존재한다. 단순히 말만 해서는 이해가 쉽지 않으므로 이또한 직접 프로그래밍 코드를 통해 생각해보고 어떻게 동작하는지 살펴보자.

우선 위의 'sample' 알고리즘을 살펴보면 tmp 변수를 통해 'sample' 알고리즘이 총 2번 호출되므로 우리는 이것을 2T만큼 호출된다고 표현할 수 수 있다. 그리고 매번 알고리즘이 재귀될 때마다 2번씩 수행되므로 2T는 계속적으로 변하지 않고 자기 호출때마다 등장하게 된다.

그러나 'sample' 알고리즘이 비록 2번씩 호출되기는 하나 해당 알고리즘은 'q'변수를 통해 매번 n/2 분할하여 연산되므로 우리는 이것을 보다 정확히 2T(n/2)라는 식으로 표현할 수 있게 된다. 이렇게 재귀부를 완성하였다면 나머지 오버헤드는 'sum'이란 변수에서 for문으로 n번 반복되는 사실을 통해 최종적으로 2T(n/2) + n이라 규정할 수 있을 것이다.

여기서 n은 인자 p와 r이 같아지기 전까지 계속해서 재귀호출을 통해 분할되게 되므로 조금 복잡하긴 하지만 알고리즘 상에서 상상해볼 때, 재귀호출된 알고리즘은 재귀되기 전 인자 n이 재귀부와 오버헤드 모두 반토막이 난 상태라 할 수 있다. 즉 분할이라는 관점에서 바로 2번째 연산식은 아래처럼 연산된다 생각하면 조금 이해가 빠르다.

이제 3번째 식까지 무사히 달릴 수 있는 암묵적 합의가 완성됬다. 헌데 4번째 식은 이게 또 무슨 장난질인가 싶을 정도로 좌절스런 짓거리가 또 한번 반복되고 있다. 이놈의 교재는 얼마나 더 못된 장난질을 해야 속이 후련하련지… 벌써부터 머리 속에서는 쌍시옷 문장들이 연발되지만 꾹 참도록 하자.

차근차근히 설명해보자면 우리는 연산식 3번째 열을 통해 해당 알고리즘에서 증가되는 상수를 모두 k로 묶을 수 있다는 사실을 알게 되었다. 4번째 열에서 이러한 변화를 수식으로 표현해내고 5번째 열에서는 2^k를 n으로 치환하여 계산해내고 있다. 그렇다면 이러한 일이 어떻게 가능하게 된 것일까? 우선 책에서 해당 부분의 인용을 먼저 보도록 하자.

단조증가함수의 가정

점근적 복잡도의 계산을 용이하게 하기 위해 자주 n=2^k이라고 가정한다(k는 양의 정수). 이 가정은 처음에는 좀 지나쳐 보일 수도 있으나 점근적 복잡도를 구한는데 전혀 지장을 주지 않는다. 이유를 설명하면 다음과 같다.
어떠한 n이라도 n과 2n 사이에 2의 멱수가 하나 있다. 즉 n≤2^k＜2n인 2^k이 하나 존재한다. 만약 임의의 상수 r에 대해 T(n)=O(n^r)이라면 T(2n)=O((2n)^r)=O(2^rn^r)=O(n^r)이므로 T(2n)=T(n)이 된다.

…중략… 

즉 입력의 크기가 두 배가 되어도 다항식 범위 안에 있는 점근적 복잡도는 변하지 않는다. 알고리즘의 복잡도 함수는 단조증가함수라 가정하므로 다음과 같다.

T(n) ≤ T(2^k) ≤ T(2n)

여기서 T(n)=T(2n)이므로 다음과 같이 된다.

T(n) = T(2^k) = T(2n)

 

단조증가함수란 함수의 진행방향이 항상 일정하다는 뜻이다. 그리고 우리는 해당 함수가 항상 일정하게 증가한다는 가정을 통해 2^k가 아무리 커진다 한들 2n을 넘을 수는 없다는 결론이 존재하기 때문에 2^k를 넉넉잡아 2^k=n로 치환 가능 가능한 것이다.

약간 어거지같은 논리같기는 하지만 이러한 추론을 통해 해당 값을 치환하지 않으면 해당 식을 빅오표기법으로 전환하기가 까다로우므로 수용하기로 하고 나머지 연산을 마치도록 하자.

T(1)=1이므로 마지막에는 n + nlogn만이 남게 된다. 왜 logn으로 떨어지는지 이해가 안된다면 정석의 로그부분을 읽으면 쉽게 감이 올 수 있다. log는 지수를 표현하는 방법이므로 2^k=n이라 할 때 log2n이 성립하게 된다.

이렇게 반복대치에 대한 모든 설명을 끝마쳤다. 사실 여기서 추정후 증명, 마스터 정리까지 모두 끝마치려 했는데 생각보다 내용이 길어져서 여기서 끊고 나머지는 다음장에서 이어서 설명하도록 하겠다.