[Logical Thinking] 4. 시간복잡도

시간복잡도(Time complexity)는 어떤 프로그램이 수행하는데 걸리는 시간을 말한다. 프로그램이 빨리 실행 될 수록 이로운 점이 많기 때문에, 우리는 시간복잡도를 줄이려고 노력한다. 프로그램이 수행하는데 걸리는 시간과 시간복잡도에 대해 알아보자. 참고로 이 글에는 이해하기 어려울 수 있는 수학적인/공학적인 내용이 들어있다. 이해하지 않고 읽기만 해도 되는 내용에는 ⁺표시를 해놓겠다. 이외의 내용은 최대한 이해하기 쉽게 작성하려고 했다.

---

프로그램의 실행 시간

최신 프로세서 들은 어느정도의 연산을 할 수 있을까? 필자가 쓰고 있는 컴퓨터의 CPU는 Intel(R) Core(TM) i7-7700HQ @ 2.80GHz 이다. 여기서 2.80GHz라는 의미는, 1초에 28억번 "클럭"을 돌릴 수 있다는 것이다. CPU는 기본적으로 하나의 클럭에 한 가지 연산을 처리한다. 쉽게 말하면, 내 CPU는 1초에 28억번 연산을 할 수 있다는 뜻이다. 물론 실제로는 그렇지 않고, 파이프라이닝이라는 것을 한다.

[그림 1] (a)는 일을 순차적으로 처리한다. (b)는 파이프라인을 통해 동시에 처리한다.

쉽게 말해서, 동시에 진행할 수 있는 일 들을 동시에 진행하는 것이다. 우리가 어떤 두 수를 더하기 위해서는, 그 두 수를 본 다음에 계산을 하고, 결과를 어딘가에 작성해야 한다. 그래서 우리가 더해야 할 두 수가 많으면, 속도를 올리기 위해서 "두 수를 보는 것", "계산 하는 것", "결과를 작성하는 것"의 세 단계로 나눠서 일을 수행하게 되고 결과를 작성하면서 두 수를 보고, 계산을 하게 된다. CPU 내에서도 이런 작업이 일어나게 된다. 이것을 "파이프라이닝"이라고 한다. 최신 CPU의 파이프라인은 13~30단계 정도이고, 하나의 파이프라인이 기본적으로 하나의 일을 하는데 걸리는 시간은 1클럭이다. 모든 연산이 모든 파이프라인을 거치는 것은 아니며, 여기서 연산들의 속도차이가 생긴다.

결론적으로 말해서, 연산 하나의 연산시간을 측정하는 것은 의미가 없고, 그 연산의 "평균적인" 연산시간을 측정하는 것이 전체 실행시간을 판단하는 데에 도움을 준다. 간단한 연산인 64bit수의 덧셈, 뺄셈 같은 것은 1클럭 정도가, 곱셈 등은 3클럭, 메모리 접근은 4~300클락, 나눗셈은 80~100 클락 정도가 걸린다. 자세한 내용은 http://www.7-cpu.com/ 등의 사이트를 참조하면 좋다.

뭐 결론적으로, 우리는 가벼운 연산들을 30억번 정도, 무거운 연산들을 1억번 정도 할 수 있다고 생각하면 된다.

---

큰 수에서의 프로그램의 실행 시간

다음 두 함수를 생각하자. 이 두 함수는 같은 입력에 대해 같은 결과가 나온다. 이 두 프로그램의 차이가 뭔지 살펴보자.

unsigned func1(unsigned n)
{
	int sum = 0;
	for(int i=0; i<=n; ++i) sum += i;
	return sum;
}

unsigned func2(unsigned n)
{
	return (unsigned long) n * (n-1) / 2 + n;
}

위의 프로그램은 덧셈, 비교라는 가벼운 연산으로 이루어져 있어서, 연산 하나하나의 실행속도가 빠르다, 반면 아래의 프로그램은 곱셈과 나눗셈(⁺사실 대부분의 컴파일러는 나눗셈을 최적화 해준다.) 으로 이루어져 있어서, 연산 하나하나의 실행속도가 느리다. 우리는 대략, 위의 프로그램이 기본 2클락에, 숫자를 한번 더 할 때 3클락 정도가 걸린다고 생각할 수 있다. 그리고, 아래의 프로그램은 입력에 관계 없이 100클락 정도가 필요하다는 것을 알 수 있다. 결론적으로, 우리는 실행시간을 n에 대한 함수로 나타낼 수 있다. 첫번째 함수의 실행시간은 T(n) = 3n+2일 것이고, 두번째 함수의 실행시간은 T(n) = 100일 것이다.

만약 우리가 쓰는 n의 범위가 0에서 10정도라면, 우리는 func1(n)을 사용할 것이다. 왜냐하면 func1은 2~32클락이 필요할 것이고, func2는 100클락이 필요할 것이기 때문이다. 하지만 만약 우리가 프로그램이 임의의 큰 n에 대해서 빠르게 돌기를 원한다면, n이 33을 넘은 시점부터는 func2가 더 빠르기 때문에, func2를 써야한다.

우리는 대부분 프로그램이 큰 입력에 대해서도 빠르게 실행되기를 원하기 때문에, func2를 사용할 것이고, 여기서 우리가 관심이 있는것은 n에 대해서 얼마나 프로그램의 실행시간이 커지는지에 대해서이다. 우리는 프로그램의 시간을 big-O 표기법으로 표현할 것이다. 이 표기법은 가장 시간이 오래 걸리는 부분에 대해서만 관심을 가진다. 첫번째 함수의 경우 T(n) = 3n + 2에서, 3n은 2보다 충분히 빠르게 커지기 때문에, 2를 무시하고 3n만 남길 수 있다. 그리고 커지는 정도에서 우리는 3이라는 숫자에 관심을 가지지 않는다. 왜냐하면, 이 숫자가 얼마나 크든 작든, 큰 수에서의 대소관계가 변하지 않기 때문이다. T(n) = an인 알고리즘과, T(n) = bn²인 알고리즘이 있으면, a와 b가 얼마나 크든 충분히 큰 n (>a/b)에 대해서, 앞의 알고리즘이 유리할 것이기 때문이다. 그래서 우리는 T(n) = 3n+2에서, 의미있는 부분인 n만 가져와서, O(n)이라고 부른다. T(n) = 100일 경우에는, O(1) 알고리즘이 되는 것이고,  T(n) = 0.00001n⁴+8n+92312312 같은 경우에는, O(n⁴) 알고리즘이 되는 것이다. (⁺좀 더 자세히 말해서, f(n) = O(g(n)) 이라고 부르는 것은, 일 때 이다.)

우리가 충분히 큰 입력에 대해서 빠르게 실행되는 것에 관심을 가지는 이유는 여러가지가 있지만, 시간을 상수배만큼 줄이는것보다, n에 관한 식으로 줄이는게 좀 더 효율적이기 때문인 것이 크다.

---

최근에 바빠서 글을 못 남기는것 같아서, 짧게 짧게라도 글을 올리는게 낫겠다고 느껴서 간단하게 올렸다. 다음 포스트에서는 시간복잡도 분석에 대해서 써 볼것이다. 게시글에 개선할 사항은 덧글로 남겨줬으면 한다.

---

이제까지의 모든 Logical Thinking 게시글 보기: http://blog.kyouko.moe/8