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

시간복잡도  의 개념을 소개하고자 합니다. 이 글에서 추가되었습니다.
모든 예시는 현대 컴퓨터의 최적화된 알고리즘과는 다를 수 있지만 이해를 위한 개념적인 예시입니다.

 

기본 개념잡기

두 수 a, b의 합, 예를 들어 123 + 456을 계산하는 과정을 생각해보겠습니다.

각 자릿수를 차례로 더하여 계산하게 되며, 이 과정은 컴퓨터 입장에서 ‘연산’이라고 부릅니다. 이 경우 3번의 연산이 수행되는데, 이는 입력값의 자릿수와 같습니다. 자릿수가 n으로 커질수록 결과를 도출하기까지 필요한 연산 횟수 역시 증가합니다. 1자리 수의 덧셈보다 20자리 수의 덧셈이 더 오래 걸리는 이유입니다. 1자리 덧셈에는 1번의 연산이 2자리 덧셈에는 2번의 연산이 필요하고, 일반적으로 n자리 수의 덧셈에는 n번의 연산이 필요합니다. 이를 일반화하면 “n자리 두 수의 각 자리를 더하여 결과를 구하는 알고리즘은 n번의 연산이 필요하다.” 라고 표현할 수 있습니다. 이 경우 이 알고리즘의 시간복잡도(Time Complexity)는 O(n)입니다. 시간복잡도라는 말은 이해가 되지만, O(n)이라는 표기가 다소 낯설 수 있습니다.

빅 오 표기법(Big-O notation)

빅오 표기법은 입력 크기 n이 커질 때, 알고리즘의 연산 횟수가 얼마나 빠르게 증가하는지를 근사적으로 나타내는 방법입니다.

예를 들어 123 + 999를 계산할 때는 자릿수 올림이 발생할 수 있습니다. 기본적으로는 3번의 연산이 필요하지만, 만약 각 자릿수마다 올림이 일어난다면 추가로 3번의 연산이 더 필요해 총 6번의 연산이 됩니다. 올림이 발생하는 횟수는 입력값에 따라 달라질 수 있습니다.
이를 a라고 하면, n자리 수의 덧셈에는 일반적으로 n + a번의 연산이 필요하다고 할 수 있습니다. (0 ≤ a ≤ n)
n이 작을 때는 a가 전체 연산 횟수에 큰 영향을 줄 수 있지만, n이 매우 커지면 a는 상대적으로 무시할 수 있는 수준이 됩니다. 즉, 연산 횟수는 n에 비례한다고 볼 수 있습니다(극한). 이러한 이유로 우리는 이 알고리즘의 시간복잡도를 O(n)이라고 표현합니다. 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) 입니다.