시간복잡도를 표현하자! Big O 표기법

- 문제의 크기와 조건

 

알고리즘 문제가 주어졌을 경우 우선 문제의 크기와 조건 고려해야 한다.

 

예를 들어 '메뉴판에 있는 모든 메뉴를 읽는데 걸리는 시간을 구하라' 라는 문제가 있을 때

 

메뉴판이 하나뿐이라면 시간은 사람수 N X 메뉴 갯수 M 만큼 걸리겠지만

사람수만큼 메뉴판이 있다고 조건이 바뀌면 메뉴 갯수 M 만큼만 걸릴테니까.

 

그렇기에 문제가 주어졌을 땐 항상 문제의 크기와 조건을 먼저 보고 방법을 생각해야 한다.

 

- 시간 복잡도

 

방법을 생각했다면 그 다음 고려해야 할 것은 시간 복잡도이다.

 

문제 해결 능력을 측정하는 알고리즘 문제 해결에선 특히 시간이 짧을 수록 효율적이라고 본다

그렇기에 문제가 주어졌을 때 떠올린 해결 방법이

최악의 경우 얼마나 시간이 걸릴지를 대문자 O를 사용하는 표기하는 Big O 표기법이 존재한다.

 

이 Big O 표기법의 특징은 최악의 경우 걸릴 시간을 대략 계산한다는 것이다.

그로 인한 두가지 특성이 있는데 하나는 상수는 과감히 버린다는 것이다. 예를 들어 

 

O(3N^2) 의 시간복잡도는 O(N^2) 으로 표기하고

O(1/2 N^2) 의 시간 복잡도도 O(N^2) 으로 표기한다.

 

다른 하나는 두가지 항이 있을 때 변수가 같으면 큰 것만 빼고 다 버린다는 것이다. 예를 들어

 

O(N^2 + N) 은 O(N^2)으로 표기하고

O(N^2 + NlgN) 도 O(N^2)으로 표기한다.

 

그러나 변수가 다른 값은 버리지 않고 놔둔다. 예를 들어 

O(N^2 + M) 같은 경우는 그대로 표기한다

 

애초에 상수나 변수가 같을 때 가장 큰 수 외의 수를 다 버리는 이유는 

그게 시간 복잡도를 계산해 구하려 하는 '최악의 경우'에 큰 영향을 미치지 않기 때문인데

N과 M처럼 아예 다른 변수는 어느 쪽이 더 작은지를 판단할 수 없기 때문이다.

 

위의 경우도 얼핏보면 N^2 부분이 이 더 클 것 같지만

N이 10이고 M이 10000이라고 하면 M 쪽이 훨씬 커진다.

그렇기 때문에 다른 변수는 어느 한 쪽을 함부로 지우지 않는 것이다.

 

위의 사항을 유의하고 1부터 N까지의 합을 계산하는 아래의 코드들과 시간복잡도를 보자

 

1.

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

시간을 들여서 일단 구현했는데 그 코드가 시간안에 수행이 안되면 거기가 바로 지옥이니까.. ㅋㅋ

 

대략적인 값이지만 N의 숫자가 1억일 경우 수행 시간이 1초 정도가 걸리니 

이를 기준으로 1초가 걸리는 입력의 크기를 정리하면 다음과 같다

 

- 대표적인 시간복잡도들의, 수행 시간이 1초가 걸리는 입력의 크기

 

O(1)

O(lgN)

O(N) : 1억

O(NlgN) : 5백만

O(N^2) : 1만

O(N^3) : 500

O(2^N) : 20

O(N!) : 10

 

- 메모리

 

메모리는 공간 복잡도를 활용해 계산할 수 있는데

메모리 제한은 보통 넉넉하기 때문에 걱정할 필요가 없다. 

불필요한 공간을 잡지 않고 시간 제한 안에만 수행되게 만들면 메모리 제한은 대부분 알아서 지켜진다