알고리즘 기초 (시간복잡도)

시간 복잡도

어떤 코드를 작성한다고 했을 때 실행 시 시간이 얼마나 걸릴지 예측하는 것을 시간 복잡도라고 한다.

▶ 문제의 크기를 N이라고 했을 때 시간이 얼마나 걸릴지 나타내는 방법을 시간 복잡도라고 할 수 있다.

• 표기법으로는 대문자 O를 사용한다. (다양한 시간 복잡도가 많지만 BIG-O를 주로 사용한다)
• 영어로는 Big O Notation → 선형시간이 걸린다고 했을 때 O(N) , N! 등
• 최악의 경우에 시간이 얼마나 걸릴지 계산한다. → 99% 실행 시 0.001초 1% 경우 100초 : 시간 복잡도는 100초

예시

• 총 N명의 사람이 카페에 방문했다.
• 카페에는 상품 개수가 M개가 있고, 메뉴판은 1개 있다.
• 사람 1명이 메뉴판을 읽는 데 걸리는 시간은 O(M)이다.
• 주문한 모든 메뉴는 동시에 나왔고 각 사람 i가 커피를 마시는 데 걸리는 시간은 Ai이다.
• 각 사람이 계산을 하는 데 걸리는 시간은 O(P)이다.
• 각 사람이 메뉴판에 있는 모든 메뉴를 읽는 시간 복잡도 = O(NM)
• 모든 사람이 커피를 다 마시는 데 걸리는 시간 = O(max(Ai))
• 티타임을 모두 마친 다음 한 줄로 서서 각자 계산을 하는 시간 복잡도 = O(NP)

▶ 시간 복잡도는 소스를 보고 계산 할 수 있기도 하고, 소스 작성 전에도 먼저 계산 가능하다.

문제를 풀기 전에 먼저 생각한 방법의 시간 복잡도를 계산하고 시간 안에 수행될 것 같은 경우에만 구현하는 것이 좋다

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

1부터 N까지 합을 하고자 할 때 작성한 코드이다. 이 코드를 실행하는 데 걸리는 시간 복잡도는 몇일까?

▶ 시간이 가장 많이 걸리는 부분은 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;
        }
    }
}

위 코드 또한 1부터 N까지 합하고자 작성한 코드이다. 일부러 복잡하게 만든 코드인데 위의 코드의 시간복잡도는 얼마일까?

▶ 변수 i N번 연산하고 i내의 j 또한 N번 연산하므로 이 코드의 시간 복잡도는 O(N²)이다.

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

위의 코드의 시간 복잡도(1부터 N까지의 합)는 얼마일까?

▶ 위의 코드는 반복하는 경우가 없고 1번만 계산하면 되기 때문에 시간 복잡도는 O(1)이다.

같은 문제에 대한 코드를 세가지로 나누어서 시간복잡도를 살펴보았다. 
O(1) > O(N) > O(N²) → O(1)과 같은 코드를 구성하도록 노력해야한다.

• 시간 복잡도 안에 가장 큰 입력 범위를 넣었을 때 1억이 1초 정도 걸린다 
• 이 값은 대략적인 값으로 실제로 구현할 때 1억을 조금 넘어도 1초 이내에 수행 가능하다.

O(N⁴) ,N<= 100 인 경우 → 시간복잡도 1억 : 1초 정도의 시간이 소요됨

N <= 500 일 경우 보통 O(N³) 시간복잡도를 만족하는 코드를 만들어야한다. → 1초 소요

1초가 걸리는 입력의 크기

• O(1)
• O(lgN)
• O(N) : 1억
• O(NlgN) : 5백만
• O(N²) : 1만
• O(N³) : 500
• O(2^N) : 20
• O(N!) : 10

시간 복잡도 계산 시 주의사항

• Big O Notation 에서는 상수는 버린다.
• O(3N²) = O(N²)
• 두 가지 항이 있을 때 변수가 같으면 큰 것만 빼고 버린다.
• O(N² + N) = O(N²)
• 두 가지 항이 있는데 변수가 다르면 그대로 둔다.
• O(N² + M) 이러한 경우는 그대로 둔다.