시간복잡도

시간복잡도는 프로그램의 수행시간을 다항식으로 나타내는 것이다.

시간복잡도는 시간제한이 있는 OJ사이트나 코딩 테스트,대회 등에서 중요한 요소이다.

하지만 대부분의 사람들은 시간복잡도를 그냥 대충 계산하는 경향이 있다.(사실 그래도 된다.)

그러나 필자는 깊이 있는 문제 풀이를 위해 시간복잡도가 굉장히 중요한 요소라

생각하기에 이에 대해 말해 보겠다.

 

1.시간복잡도 계산

그 프로그램에 있는 반복문의 반복 횟수라 봐도 문제가 없다.

arr[1]과 같은 한 번에 접근 가능한 것을 O(1)의 시간복잡도를 가졌다 하고,

이는 그 프로그램의 시간복잡도에서 보통 생략된다.

예를 들어보자.

n=int(input())
for i in range(n):
	print(i)

다음의 코드는 i가 0부터 n까지 1씩 증가하는 코드이다. 

이때 반복은 총 n번 돌기에 이 코드의 시간복잡도는 O(N)이다.

 

2.일반적인 시간복잡도

초보자 단계에서 정렬의 시간복잡도는 O(N^2)

<<bubble sort와 같은 것들이다.

주로 쓰이는 정렬의 시간복잡도는 O(N log N)

<<merge sort와 같은 것들이다.

특수한 상황에서 정렬

<<counting sort가 대표적이다.O(N+K(가장 큰 수))

 

3.정리

그 프로그램의 반복을 하나의 다항식으로 만들어라.

이때 O(1)과 같은 상수는 생략한다.

 

4.여담

빅오메가,빅세타 표기법도 존재한다.

빅오메가는 최선의 상황일때의 반복을 표기하고

빅세타는 평균적인 상황일때의 반복을 표기한다.

하지만 대부분의 문제에서 최악의 경우를 상정하기에

빅오표기법을 주로 사용한다.

예를 들면 랜덤한 수를 뽑을때 0이 되면 종료인 프로그램은

한 번에 될 수도 있기에 빅오메가의 경우에는 이 프로그램은 Ω(1)이다.

(다른 문자가 없으니 1을 남겨두겠다).

하지만 영원히 안 뽑힐수 있는 상황이 있기에

O(무한)이 이 프로그램의 빅오-시간복잡도 이다.