시간복잡도 - 실생활 예시로 개념잡기

시간복잡도 란 단어를 처음 들어본 입장에서 개념을 소개하고자 합니다.
모든 예시는 현대 컴퓨터의 최적화된 알고리즘과는 다를 수 있지만 개념적으로 이해하기 위한 예시입니다.

 

기본 개념잡기

두 수 a, b의 합에 대해 생각해 보도록 하겠습니다. 간단히 123 + 456라고 해보겠습니다.

이를 계산하기 위해서 사람은 각 자리를 더하여 결과를 계산합니다.

각 자리를 더하는 과정은 컴퓨터의 계산이 필요한 부분으로 이를 연산이라고 합니다. 위 과정은 3번의 연산을 수행하게 됩니다. 이 3은 입력값의 자릿수와 같습니다.

만약 자릿수 n이 커지면 커질수록 답을 도출하는 연산도 많아집니다. 연산이 많아진다는 것은 결과 도출 시간도 오래 걸린다는 얘기입니다. 1자리 수 덧셈보다 20자리 수 덧셈이 더 오래 걸리는 것과 같습니다. 1자리 수 덧셈에는 1번의 연산, 2자리 수 덧셈에는 2번의 연산,..., n 자릿수 연산에는 n번의 연산이 필요합니다. 

일반화하면 'n자리 수에 대해 각 자리를 더한 결과를 합쳐 최종 덧셈 결과를 도출하는 알고리즘은 n번의 연산이 필요하다.'라고 표현할 수 있습니다.

이를 간략히 이 알고리즘은 시간복잡도(Time complexity)가 O(n)라고 합니다. 시간복잡도가 왜 시간복잡도인지는 알겠는데 O(n)은 표현이 다소 어색합니다.

빅 오 표기법(big-O notation)

빅 오 표기법(big-O notation)이라고 불리는 이 표기법은 변화하는 n에 대해 n이 무한대로 커질 때의 근사한 연산 횟수를 표기하는 방법입니다. 위의 덧셈 예시에서 한 가지 슬쩍 넘어간 부분이 있는데 바로 자릿수 올림입니다. 123 + 456은 다행히도 각 자리의 덧셈에서 자릿수 올림되는 경우가 없었습니다. 하지만 123 + 999처럼 자릿수 올림이 발생하는 경우에는 올림에 대한 연산을 추가로 수행해주어야 합니다. 이 경우 기존 3번의 연산과 올림에 대한 연산 3번이 추가로 수행될 것입니다.

자릿수 올림 연산 횟수는 주어진 입력값에 따라 달라집니다. 올림 연산의 횟수를 a라고 했을 때, n자릿수 연산을 일반화하면 n+a (0 ≤ a ≤ n) 번의 연산이 필요하다고 할 수 있겠습니다.

여기서 극한의 개념이 등장합니다. n이 작은 경우에는 a번 연산들이 전체 연산 횟수에 유의미한 차이를 만들지만 n이 커질수록 n번의 연산이나 n + a번의 연산이나 연산 횟수에 큰차이가 없게됩니다. 결국 연산의 횟수는 n으로 근사하게 되고, 이 값을 표현하기 위해 빅 오 표기법을 사용합니다. 표기는 O(n)과 같습니다.

 

이해를 위해 간략한 예시를 몇가지 들어보겠습니다. 

1. O(1) - 선형 시간 복잡도

주어진 두 수의 두번째 자리까지의 덧셈 결과를 반환하는 함수가 있다고 가정해보겠습니다.  자리수 n이 아무리 커져도 항상 일정한 2 + a번연산 횟수를 가지게 됩니다. (= 연산에 걸리는 시간도 항상 일정합니다.) 이를 n과 관계없이 일정한 시간복잡도를 갖는다고 하여 O(1)이라고 표기합니다. 여기서 1은 1번이라는 뜻이 아닌, 일정하다는 뜻입니다.

 

2. O(n^2)

두 수의 곱셈에 대한 연산은 시간복잡도가 어떻게 될지 생각해보겠습니다. 사람들은 일반적으로 12 * 45 을 계산하기 위해서 다음과 같이 계산합니다.

 

 

선행 수의 자리수 각각에 후행 수의 곱셈 연산을 모두 수행하고 더해줍니다. 대략 n^2 + an + b 같은 꼴이 될 수 있습니다.

n이 커질수록 대략 n^2번의 연산이 필요함을 알 수 있습니다. 결국 최고차항의 계수만 반영되어 O(n^2)으로 표기할 수 있습니다.

 

정렬 알고리즘에서의 시간복잡도

개념적인 이해는 모두 끝났으니 데이터 정렬 알고리즘에서의 시간복잡도로 마무리하겠습니다.

1부터 10까지 수를 랜덤으로 나열합니다. 7 5 9 10 4 2 1 8 3 6 과 같습니다.

이를 정렬하는 방법은 여러가지가 있을텐데, 가장 직관적인 방법으로 다음과 같은 방식이 있습니다.

1. 배열의 첫번째 자리부터 열번째 자리까지 둘러보며 가장 작은 수(=1)를 찾고, 배열의 첫번째 자리의 수(=7)와 교환한다. 

2. 배열의 두번째 자리부터 열번째 자리까지 둘러보며 가장 작은 수(=2)를 찾고, 배열의 두번째 자리의 수(=5)와 교환한다.

3. 배열의 세번째 자리부터 열번째 자리까지 둘러보며 가장 작은 수(=3)를 찾고,  ...

...

10. 배열의 열번째 자리부터 열번째 자리까지 둘러보며 가장 작은 수(=10)를 찾고, 배열의 열번째 자리의 수(=10)와 교환한다.

1단계에서 나열된 모든 수를 둘러봐야 가장 작은 수인 1을 찾을 수 있습니다.

둘러본다는 것은 컴퓨터가 현재의 최소값과 배열의 n번째 요소의 크기를 비교연산한다는 뜻으로, 결과적으로 컴퓨터는 10번의 연산이 필요합니다. 따라서 위 정렬을 위한 총 연산은 아래 그림과 같습니다.

참고로 위 랜덤 숫자 정렬 예시는 선택정렬과 거의 유사한 방식입니다.

선택정렬은 위에 수행한 각 열번의 과정에서 i번째 연산에서의 i번째 값은 최소값을 담을 변수에 저장만 할 것이므로 (연산하지 않으므로) 선택정렬의 수행횟수 식은 ( N - 1 ) * N / 2 입니다. 따라서 선택정렬의 시간복잡도 역시 O(N^2) 입니다.