알고리즘 기반 지식 : 복잡도 측정

알고리즘은 문제를 정확하게 해결하는 것이 중요하다. 이때 정확하게 해결한다는 의미는 답을 얻기만 하면 된다는 의미가 아니다. 적당한 시간내에 답을 얻을 수 있어야 한다는 것을 의미한다. 어떤 알고리즘은 컴퓨터를 동원하더라도 수십년 혹은 수백만년이 걸릴 수 있다. 반면 동일한 문제를 푸는데, 하루 혹은 몇 시간이 걸리는 알고리즘을 만들 수도 있다. 아주 간단한 문제가 아니라면, 문제를 풀기 위한 두 개 이상의 알고리즘이 존재하기 마련이다. 소프트웨어 개발자는 어느 알고리즘이 더 나은지를 판단하기 위해서 알고리즘에 필요한 시간을 측정 할 방법이 필요하다.

알고리즘을 평가하기 위해서 문제의 크기와 관련해서 실행시간이 어떻게 변하는지를 알아야 한다. 배열에서 가장 큰 원소를 찾는 find_max()함수가 있다고 가정해 보자. 10개의 원소를 가지고 있을 때의 시간과 1000개의 시간을 가지고 있을 때 얼마만큼의 시간이 걸릴지를 평가 해야 한다. 원소가 100배 늘어나면 100배 만큼의 시간이 걸리는지 혹은 10, 5배만큼의 시간이 걸리는지 아니면 1000 배만큼의 시간이 걸리는지를 측정해야 한다. 이 시간을 알고리즘에 대한 시간 복잡도(time complexity)라고 한다.

데이터 크기(size)별 알고리즈이 걸리는 시간은 그래프를 이용해서 간단하게 나타낼 수 있다. 성능측정이라고 부르기도 한다. 예컨데 1에서 1000 사이의 데이터 목록에 대해서 find_max()를 수행하고 그 결과를 측정하면, 데이터 크기별 걸리는 시간을 시각화 할 수 있을 것이다. 이 방식은 아래의 문제점들이 있다.

1. 컴퓨터는 서로 다른 속도로 작업을 수행한다. 더하기는 매우 빠르지만 나누기는 매우 느리다. 그리고 이 속도는 컴퓨터의 목적에 따라서 달라질 수 있다. 어떤 컴퓨터는 수학연산을 매우 빠르게 할 수 있지만, 문자열 연산은 (수학 연산에 비해서)매우 느릴 수 있다. 또한 컴퓨터에 따라서 메모리 크기, 프로세서, 디스크 속도가 다르다. 측정하는 사람에 따라서 다른 결과가 나올 수 있다.
2. 주어진 범위에서의 성능측정은 결국 경험의 수치화다. 경험하지 않은 범위에 대해서 성능이 계속 확장될지 알 수 없다. 1에서 1000까지는 빠르다고 해서 10000~20000 범위에서 빠를 것이다라고 장담할 수 없다.

복잡도는 big-O 표기법으로 나타낸다. Big-O표기법에서 복잡도는 "O(<어떤 함수>)" 방식으로 표시하는데, 연산의 수는 주어진 함수에 상수요소를 곱한 값에 비례한다. 예를 들어 알고리즘이 2 * (n**2) 연산을 수행하는 경우 복잡도는 O(n**2)가 되며 상수 배수는 2가 된다.

널리 사용하는 복잡도를 정리했다.

• O(1)은 상수시간 복잡도를 의미한다. 문제의 크기가 커져도 알고리즘 작동 횟수는 변하지 않는다.
• O(log n)은 로그 복잡도를 의미한다. 보통 log_2 혹은 lg를 사용한다. 로그 복잡도를 가지는 알고리즘은 특히 대수적인 복잡성을 가지는 문제에 효율적으로 대처한다.
• O(n)은 선형 복잡도를 의미한다. 문제의 크기가 두 배가 되면, 2 배만큼의 연산이 필요하다.
• O(n**2)는 문제의 크기를 두 배로 늘리면 작업수가 4배가 된다. 10배로 늘어나면 100배 더 많은 작업수가 필요하다.
• O(n**3), O(n**4), O(n**5) 다항식 복잡도다.
• O(2**n)은 지수적 복잡도를 의미한다. 문제 크기를 1단위로 늘리면 작업이 두 배가 되고, 2단위 늘리면 4배가 된다. 작업의 양이 빠르게 증가하기 때문에, 문제 크기가 매우 작은 경우에만 사용 할 수 있다.

Big-O 표기법을 만들 때, 계산 요소가 많다면 문제의 크기 변화에 따라서 빠르게 증가하는 계산 요소만 사용 하고 나머지는 생략 할 수 있다. 예를 들어 O(n**2 + 10n + 5)가 있다면 O(n**2)로 써도 된다. 10n + 5는 계산 증가에 기여하는 바가 매우 작기 때문이다. n이 100배가 증가하면 n**2 항은 작업을 10,000배 증가시킨다. 같은 기간에 10n+5는 1,000 건이라서 그다지 영향을 미치지 않는다.

알고리즘이 제대로 작동하는 걸 확인 한 후에는 시간 복잡성이 가장 중요한 알고리즘 평가 요소이지만, 알고리즘이 사용하는 메모리나 저장공간의 양이 중요할 수도 있다. 이들 공간 복잡도 역시 big-O 표기법으로 사용 할 수 있다. A 알고리즘이 있다고 가정해 보자.

1. O(n) 시간을 가지며, O(1)의 메모리 공간을 사용한다.
2. O(n) 만큼의 메모리 공간을 사용하면, O(1) 시간을 소비하도록 바꿀 수 있다.

이 경우 실행환경에 따라서 알고리즘 선택이 달라질 수 있다. 핸드폰의 경우 메모리가 부족하므로 속도가 느려도 적은 메모리 사용이 가능한 첫 번째 알고리즘을 선택해야 할 것이다. 데스크탑 컴퓨터라면 메모리가 충분하므로 더 빠른 속도를 위해서 두 번째 알고리즘을 사용해야 할 것이다.