[Algorithm] 어떤 알고리즘이 더 빠르고 효율적인가? - 시간복잡도 (1)

세상은 복잡하다, 우리의 문제도 그렇다.

1. 서론

알고리즘의 정의를 뜯어보자면, "어떤 문제의 해결을 위하여, 입력된 자료를 토대로 원하는 출력을 유도하여 내는 규칙의 집합"을 의미한다. 결국, 하나의 문제를 해결하는 규칙 / 방법이라고 요약할 수 있겠다.

 

컴퓨터가 인류의 역사에 나타나면서 인류는 컴퓨터의 도움으로 해결할 수 있는 일련의 규칙 혹은 방법을 체계화하였다. 컴퓨터 시대의 태동 속에서, 누구의 규칙이나 방법이 다른 규칙 / 방법에 비해 더 좋은 방법을 가지는지에 대한 궁금증은 하나의 중요한 주제로 떠올랐다.

 

스스로 생각해보자, 외부 요인이 같다는 가정 하에 어떤 알고리즘이 다른 알고리즘보다 뛰어나다는 것은 무엇을 의미할까?

 

예를 들어, 1부터 (1억 + 1) 까지의 홀수들의 합을 구하는 알고리즘을 떠올려보자. ( $ 1+3+5+\cdots +100000001 $ )

 

누군가는 하나씩 더해가면서 합을 구할 것이다. 또 다른 누군가는 수학자 가우스처럼 1과 (1억 + 1)을 짝지어 합이 같다는 점을 이용하여 합을 구할 것이다. 또 다른 누군가는 홀수들의 합은 어떤 수의 제곱과 일치하다는 점을 이용하여, 한 번의 연산으로 합을 구할 것이다. ($ 1+3+5+\cdots + (2n-1) = n^{2} $)

 

셋 중에 더 좋은 알고리즘을 사용한 사람은 누구인가? 또 왜 좋은 알고리즘은 좋은 알고리즘인 것인가?

 

더 빠른 시간 내에 해결? 더 효율적인 공간 활용? 아니면 시간 효율/ 공간 효율의 적절한 조화? 더 적은 연산 수행 횟수?

 

어떤 것이 기준이 될 지는 모르지만, 직감적으로 한 번의 연산이 무식하게 하나씩 더 한 것보다 더 좋은 알고리즘이라는 것은 자명하다.

 

컴퓨터공학자들과 수학자들은 이에 대하여 하나의 약속을 정했는데, 연산의 횟수가 적은 것을 하나의 기준으로 삼았다. 이 방법은 컴퓨터의 속도나 메모리에 영향을 받지 않는 기준이기에 널리 사용되기에 적합하였다.

 

어떤 문제를 일반화하였을 때, 이 알고리즘이 (대략) 몇 번의 연산으로 해결이 되는지를 기준으로 나타내며, 우린 이것을 시간 복잡도(Time complexity)라고 부른다.

---

2. 시간 복잡도 / 공간 복잡도

시간 복잡도란 개념은 일반화된 상황이라는 것을 가정하여, 대략 얼마나 오래 걸릴지 추측하는데 하나의 지표가 되는 개념이다. 연산의 횟수는 연산 시간과 어느 정도의 상관관계를 가지기 때문이다.

 

대략이라는 글자를 계속 강조하는 이유는, 시간 복잡도를 계산하는데 그렇게 많은 정확함을 요구하진 않기 때문이다. "이 정도의 시간복잡도면 이 정도 시간안에 대략 끝나겠구나" 정도 추측하는 데 하나의 지표가 된다.

 

또, 만약 시간 복잡도가 비슷하거나 같다면, 더 효율적인 알고리즘은 메모리를 더 적게 사용하는 알고리즘이라고 생각할 수 있다. 우린 이를 공간 복잡도(Space complexity)라고 부른다.

 

그렇지만 공간 복잡도는 시간 복잡도에 비해 그렇게 비중을 크게 두지 않는데, 공간(메모리)는 돈으로 해결할 수 있지만, 속도는 그렇지 못하기 때문이다.

 

그럼, 시간 복잡도라는 것은 구체적으로 어떻게 나타낼까에 대한 의문이 생긴다. 컴퓨터공학자들은 수학에서의 점근적 표기법 중 빅-오 표기법(Big-O notation)을 활용하였다.

---

3. Big-O Notation

컴퓨터는 기본적으로 굉장히 큰 수의 연산 횟수를 수행할 때 사용한다고 생각할 수 있다.

 

따라서, 어떤 알고리즘이 다른 알고리즘보다 효율적이다라고 말할 때는 매~~~우 반복적인 연산 및 매~~~우 큰 입력의 상황에서도 적용되어야 한다.

 

만약, $ n $의 크기를 가진 입력에 한 알고리즘은 $ 100n^{2} + 17n + 4 $ 만큼의 수행시간을 가지고, 다른 알고리즘은 $ n^{3} $만큼의 수행시간을 가진다고 하면, 어떤 알고리즘이 더 빠른가?

 

빨간색 : $ 100n^{2} + 17n + 4 $  // 파란색 : $ n^{3} $ 의 그래프

 

처음에는 빨간색 그래프가 파란색 그래프보다 더 위에 있으므로, 파란색 알고리즘이 더 효율적이라는 것을 알 수 있다. 그러나 $ n $이 100이 넘어간다면?

 

빨간색 : $ 100n^{2} + 17n + 4 $  // 파란색 : $ n^{3} $ 의 그래프

 

파란색 그래프가 빨간색 그래프보다 더 위에 있는 모습을 확인할 수 있다. 다른 말로, 입력의 크기가 100 이상이 되면 더 이상 $ n^{3} $ 알고리즘이 $ 100n^{2} + 17n + 4 $보다 효율적인 알고리즘이 아니라는 의미이다.

 

컴퓨터 연산은 $ n $이 매우 큰 상황이 대다수이기에 $ 100n^{2} + 17n + 4 $ 의 연산 수행 알고리즘이 더 좋은 효율을 낼 가능성은 매우 크다.

 

$ n $이 매우 큰 상황일 때 $ 100n^{2} + 17n + 4 $ 은 대략 $ n^{2} $에 근사하다고 할 수 있고, 이를 우리는

 

$$ 100n^{2} + 17n + 4 = O(n^{2}) $$

 

라고 표현하기로 약속하였다. 이를 우린 빅-오 표기법(Big-O notation)이라고 부르기로 하였다.

 

빅-오 표기법의 엄밀한 정의는 다음과 같다.

---

$f$와 $g$ 가 정의역이 정수 혹은 실수의 집합이고, 공역이 실수의 집합인 함수에서, $x > k$이고 $ \left|f(x) \right| \leq C \left| g(x)\right|$ 를 만족하는 상수 $C$ 와 $k$ 가 존재할 때, $f(x) = O(g(x))$라 부른다.

---

무슨 말인지 모르겠다면, 대략 $x$가 무한히 커짐에 따라 $Cg(x)$ 보다 $f(x)$가 더 천천히 증가한다고 이해하면 된다.

 

$x > k$ 에서 $ \left|f(x) \right| \leq C \left| g(x)\right|$를 만족하는 상수 $C, k$는 무수히 많기에, 단 하나 만족하는 상수 $C, k$의 조합이 있다면 적당히 사용하면 된다.

 

예제를 하나 생각하여보자.

 

3-1) Example 1

$f(x) = x^{2}+2x+1$은 $O(x^{2})$임을 보이시오.

 

언제나 시간 복잡도를 따질 때는 대략 이라는 것이 하나의 포인트이다. 따라서, $f(x) = O(x^{2})$이도록 적당한 상수 $C, k$를 찾으면 된다.

 

$x > 1$ 일 때 $x^{2} > x$ 이고 $x > 1$ 이므로 다음의 부등식이 성립한다.$$0 \leq x^{2}+2x+1 \leq x^2 + 2x^2 + x^2 = 4x^2$$따라서, $C = 4, k = 1$이라고 하면 $f(x) = O(x^2)$이라고 표현할 수 있다.

 

위의 식에서 등식($=$)이라고 해서 정말 $f(x)$와 $O(x^2)$가 같다는 것이 아니라, $n$이 무한히 커짐에 따라 두 식은 비슷한 속도로 증가한다는 개념으로 이해하고 넘어가면 된다.

 

시간 복잡도에 대한 개념이 어느 정도 이해 되는 것 같으면 다음 글로 넘어가자.