'내가 작성한 로직의 복잡도는 얼마나 될까?'

중요한 로직을 작성할 때면 머릿속에서 떠오르는 질문이다. 복잡도를 통해 로직의 성능을 예측할 수 있기 때문에 코드를 통해 복잡도를 유도하는 과정은 꽤 중요하다고 할 수 있다. 그러나 로직이 방대하고 다양한 자료구조를 사용할수록 복잡도를 계산하기란 쉬운 일이 아니다. 만약, 복잡도를 구했다고 하더라도 계산한 복잡도가 맞는지 의문이 들 때가 많다.

최근 알고리즘을 다시 공부하면서 실험을 통해 복잡도를 예측하는 방법에 대해 알게 되었다. 더블링 테스트 또는 두 배 비율 실험(DoublingRatio 실험)이라 불리는 방법이다. 개인적으로 더블링 테스트가 조금 더 직관적으로 다가오기 때문에 더블링 테스트라고 부르겠다.

알고리즘 복잡도의 중요성

더블링 테스트에 대해 알아보기 전에 알고리즘의 복잡도가 왜 중요한지 다음의 상황을 상상하며 고민해보자.

복잡도가 $O(n^2)$인 알고리즘을 사용하는 일괄처리 애플리케이션이 있다. 해당 애플리케이션은 하루 안에 주어진 작업을 처리하면 되는데, 현재 수 시간이면 그 작업을 끝낸다. 그런데, 한 달 뒤 지금보다 10배 많은 사용자가 서비스를 사용할 것이라고 예측됐다. 이에 대응하기 위해 개발자는 일괄처리 애플리케이션이 돌아가는 장비를 10배 더 빠른 장비로 교체했다. 개발자의 선택은 옳았을까?

한 달이 지났고 사용자는 예상대로 10배 더 많아졌다. 입력값이 10배가 되니 수 시간 걸리던 작업이 기존 장비에서는 수 주 동안 처리되고 있었다. 그나마 다행히 10배 빠른 장비에서는 딱 하루가 걸렸다. 그러나 개발자의 고민은 이제 시작이다. 여기서 트래픽이 10배 더 증가한다고 했을 때 더는 10배 더 빠른 장비로 커버할 수 없단 걸 직감했기 때문이다.

위의 상황이 알고리즘의 복잡도가 얼마나 중요한지 잘 보여준다. 복잡도가 $O(n^2)$ 이상이면 문제 크기가 커질수록 실제 환경에서 사용하는데 많은 제약이 따른다. 특히, 위의 상황처럼 입력 크기에 따른 영향도가 컴퓨터 속도 증가율을 압도하기 때문에 일정 입력값 이상으로는 물리적으로 처리할 수 없게 된다. 즉, 원하는 시간 내에 로직을 처리할 수 없다. 만일 위 예시의 일괄처리 애플리케이션이 복잡도가 $O(n\log{}n)$ 이하인 알고리즘을 사용했다면 사용자가 증가하더라도 별다른 조치없이 충분히 대응 가능했을 것이다.

더블링 테스트 (DoublingRatio 실험)

복잡도의 중요성을 알았으니 실험을 통해 복잡도를 예측하는 방법인 더블링 테스트에 대해 알아보자. 더블링 테스트는 이름 그대로 입력의 크기를 2배씩 키우며 진행된다. 입력의 크기를 2배씩 키우며 실행 시간을 측정한 뒤 직전 실행 시간과의 비율을 계산해나간다. 이 비율이 $2^b$ 한계에 도달할 때까지 실험을 계속해 나간다. 한계에 도달했을 때 대상 알고리즘의 실행 시간 증가 오더(복잡도)는 근사적으로 $N^b$가 된다고 예측할 수 있다.

실험

실제 실험 결과를 통해 확인해보자. 소스 코드는 다음의 링크를 통해 확인할 수 있다.

• 실험 코드: DoblingTest.java
• 실행 코드: DoblingTestTest.java

실험 결과

입력 크기	실행 시간	비율
250	0.0	2.8
500	0.0	3.0
1000	0.3	6.6
2000	2.2	8.0

실험의 결과로 실행 시간 비율이 8에 근접했다. 즉, $2^3$ 한계에 도달했고 이를 통해 해당 알고리즘의 시간 복잡도가 $O(n^3)$ 이라고 예측할 수 있다.

실제 실험을 해보면 비율이 깔끔하게 떨어지지는 않는다. 우리가 작성한 코드가 컴파일되거나 실행되는 과정에서 다양한 방법의 최적화가 일어나기 때문이다. 예를 들어 자주 접근하는 값은 캐싱 처리되어 더 빨리 접근할 수 있도록 동작할 것이다. 그러나, 실험을 여러 번 하다 보면 어느 정도 일관된 결과를 관측할 수 있고 이를 토대로 복잡도를 유추할 수 있다. 또한 이런 영향도를 줄이기 위해 입력값을 무작위로 설정하는 것이 좋다.

더블링 테스트 증명

이 방법이 정말 믿을 만 한 것인지 수학적 접근을 통해 증명해보자.

임의의 알고리즘에 대한 시간 복잡도를 틸다(Tilda) 근사로 일반화하면 다음과 같다.

더블링 테스트는 다음의 값을 통해 복잡도를 유추한다.

이 식에 일반화된 시간 복잡도를 대입하여 계산하면 증명은 끝난다.

즉, $T(2N)/T(N)$는 $2^{b}$로 근사하고 $b$는 $N$의 지수다.

실험의 중요성

더블링 테스트를 통해 살펴본 것처럼 알고리즘 분석은 과학적 방법론을 따른다. 관찰하고 측정한 뒤 가설을 세우고 예측한다. 그리고 실험을 통해 그 예측이 맞는지 검증한다. 가설과 관찰이 합치될 때까지 가설 수립과 관찰 과정을 반복한다.

알고리즘 분석을 넘어 프로그램 개발 전반적인 활동에서 과학적 방법론을 실천할 필요가 있다. 프로그램 개발은 곧 컴퓨터 공학이고 공학은 과학을 기초로 하기 때문이다. 과학을 기초로 한다는 말은 실험이 기본이라는 뜻이다. 알고리즘 성능을 실험하는 더블링 테스트뿐만 아니라 코딩을 포함한 개발 활동에서 실험은 일상화되어야 한다. 새로운 라이브러리, 프레임워크, 설계 등 많은 것들이 홍수처럼 쏟아지고 있다. 이러한 상황에서 단순히 정보를 받아들이기보단 직접 사용해서 실험해보며 어떤 것이 더 좋은지 눈으로 확인하는 자세가 필요하다.

참고문헌

로버트 세지윅, 케빈 웨인. 알고리즘(개정판 4판). 길벗, 2018.