[자료구조] 시간복잡도 함수 T(n), 빅오 표기법 O(n)

 

바퀴가 굴러간다고 해서 차 개발이 끝난게 아니듯이 문제를 해결하는 코드를 짰다고 해서 다 끝난게 아니다. 프로그래머는 계속해서 더 좋은 코드를 짜내야 한다. 그렇다면 좋은 코드, 즉 좋은 알고리즘은 어떤 것일까?

 

좋은 알고리즘의 기준은 크게 세가지다.

1. 잘 알아볼 수 있게 짰는지

2. 수행시간이 빠른지

3. 프로그램을 실행할 때 사용하는 메모리가 작은지

 

 

이번 글에서는 두번째 기준인 수행시간에 대해 좀 더 설명하고자 한다.

 

 

수행시간 측정방법(알고리즘 복잡도 분석법)

먼저 코드의 수행시간을 줄이기 위해서는 수행시간을 측정할 수 있어야 한다. 가장 단순하고 확실한 방법은 직접 측정해보는 것이다. c언어에서는 #include <time.h> 헤더파일을 이용해 쉽게 시간을 측정할 수 있다. time함수를 입력해서 컴파일 후 실행하면 특정 코드의 수행 시간이 출력된다. 하지만 이 방법을 사용하려면 출력이 되는 코드를 짜야만 한다. 이 말은 즉 오류 없는 완성형 코드를 만들어야 한다는 것이다. 시간을 측정하고 싶을때마다 하나하나 작성하는 것은 매우 귀찮다. 다행이 이 방법 말고도 수행시간을 대략적으로 알 수 있는 좋은 방법이 있다.

 

코드의 수행 횟수를 세면 된다. 산술연산, 대입연산, 비교연산 모두 연산 한개당 1번으로 간주한다. 수행 횟수가 클수록 수행시간은 늘어난다.

// 알고리즘 복잡도 분석법 예

name = ( 1 + 2 ) ;   대입연산 1번, 덧셈연산 1번 총 2번


if ( a < b )
{
   a = b ;		비교연산 1번, 대입연산 1번 총 2번
}


for (i=0; i<n; i++)    대입연산 1번, 비교연산 n+2번, 덧셈연산 n+1번 총 2n+4번

이것을 알고리즘 복잡도 분석법이라고 한다.

 

 

 

시간복잡도 함수 T(n)

 

이제 수행시간을 측정할 수 있게 되었다. 그런데 아직 어떤 알고리즘의 수행시간이 짧은지는 판단하기 애매하다. 입력 값에 따라 수행 횟수가 달라지기 때문이다. 예를 들어보겠다. 3을 n번 더해주는 함수에 n=3을 넣으면 수행횟수는 3이다. 하지만 n=4를 넣으면 수행횟수는 4가 된다. 따라서 알고리즘 복잡도 분석법으로 구한 수행시간은 n에 대한 함수로 정의해야 한다. 이처럼 수행 횟수를 입력의 개수 n의 함수로 나타낸 것을 시간복잡도 함수라고 하고 T(n)이라고 표기한다. 이제 어떤 알고리즘의 수행시간이 더 짧은지 비교해보겠다.

 

알고리즘A의  T(n) = n

알고리즘B의  T(n) = 5√n

 

x축은 n, y축은 수행시간이다

n<25 인 경우 알고리즘A의 수행시간이 더 짧다. 하지만 n>25인 경우 알고리즘B의 수행시간이 더 짧다.

둘 중 어느 알고리즘이 더 효율적일까? 제일 짧은 수행시간인 최선의 n이 나오면 좋겠지만 항상 그럴 수는 없다. 따라서 제일 긴 수행시간이 나오는 최악의 n을 기준으로 판단해야 한다. 따라서 위의 두 알고리즘 중 B의 알고리즘이 더 효율적이다.

 

빅오 표기법 O(n)

 

최악의 n은 n이 무한대인 경우다. n이 무한대로 가면 차수가 가장 큰 항이 가장 영향을 크게 미친다. 따라서 가장 큰 차수만 찾으면 계수와 나머지 항들은 무시해도 된다. 이런 방법을 빅오 표기법이라 하고 O(n)라고 표기한다.

 

 

다음은 많이 쓰이는 빅오 표기법이다.

 

 

T(n) -> O(n)  예시

 

T(n) = 10                     ->    O(1)

T(n) = 10n^2 + 5n        ->   O(n^2)

T(n) = 5n^3 + 3n + 3    ->   O(n^3)

 

 

 

O(n) 수행시간 비교

 

                          O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!)

 

 

 

 

 

 

 

참고자료

c언어로 쉽게 풀어쓴 자료구조