[Algorithm] 시간 복잡도

시간복잡도(BigO)가 얼마나 나오는지 생각해야 한다.

같은 문제라도 푸는 방법은 여러가지가 있다.

같은 문제라도 어떤 방법을 선택하는지에 따라 수행에 걸리는 시간이 크게 차이난다.

일반적으로 알고리즘에선 1억의 시간복잡도(연산횟수)를 어림잡아 1초정도 걸릴거라고 본다.

 

이 등가개념은 개인용 PC의 CPU 연산속도를 근거로 나온 수치인데,

현대의 상용 CPU는 대충 초당 1억번의 연산을 하기 때문이다.

 

1부터 N까지 수의 합을 구하시오.

 

// 시간복잡도 O(N²)

int sum = 0;

for (int i = 1; i <= N; i++) {

   for (int j = 1; j <= N; j++) {

     if (i == j) {

     sum += j;

    }

  }

}

 

// 시간복잡도 O(N)

int sum = 0;

for (int i = 1; i <= N; i++) {

     sum += i;

}

 

// 시간복잡도 O(1)

int sum = 0;

sum = N * ( N + 1 ) / 2;

 

입력값 N에 대해 2중 for문으로 돌려 푼 1번 방법은 O(N²)의 시간복잡도가 나온다.

입력값 N에 대해 for문 한번으로 푼 2번 방법은 O(N)의 시간복잡도가 나온다.

입력값 N에 대해 수학공식을 대입한 3번 방법은 O(1)의 시간 복잡도가 나온다.

 

예를들어 1부터 10만까지 수의 합을 구하여야 한다면,

1번 : 10만 x 10만 = 100억
2번 : 10만 = 10억
3번 : 10만 = 1

 

이 값들을 가지고 수행시간을 예상해본다면

1억 = 1초이므로

 

1번 : 100억 = 100초
2번 : 10만 = 0.001초
3번 : 1 = 즉시(이루 말할수 없이 빠름)

 

이라는 예상값을 도출해낼 수 있다.