시간 복잡도와 빅오 표기법(Big-O Notation)

시간 복잡도

코드의 실행 시간이 어떤 요인으로 결정되는지 나타내는 시간과 입력 데이터의 함수 관계

 

빅오 표기법

알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계를 표기

 

 

1초라는 시간이 주어졌을 때 입력 조건에서 명시되어 있는 최악의 경우를 시간 복잡도에 대입해 보았을 때 1억이 넘지 않은다면 실행 시간이 1초보다 빠른 충분히 효율적인 코드일 가능성이 높다. N값이 최대 1만이라고 했을 때 작성한 코드가 O(N²)의 시간 복잡도를 갖는다면 N을 대입했을 때 1억이 되기 때문에 시간 제한을 맞추지 못할 가능성이 매우 크다. (1억은 절대적인 기준이 아니다.)

 

 

시간 복잡도 계산하기

보통 입력되는 값들을 순회하면서 처리하는 데 반복문이 사용된다. 따라서 사용되는 반복문이 어떤 값에 비례해서 반복하는지 따져 보면 시간 복잡도를 계산할 수 있다.

 

시간 복잡도는 실행 시간이 어떤 요인으로 결정되는지 나타내는 수식일 뿐이다. 따라서 시간 복잡도에서는 곱하거나 더해지는 상수 부분은 나타내지 않는다.

 

길이가 N인 배열의 반만 사용하는 알고리즘이 있다고 했을 때, 반복 횟수는 N/2이다. 빅오 표기법으로 O(N/2)로 나타낼 수 있지만 상수 부분을 제외하고 O(N)으로만 표기한다. N에 비례한다는 것을 나타내기 위해서이다.

 

반면 배열을 M번 반복해야 한다면 M은 무시해서는 안 된다. 이 경우에는 길이 N인 배열을 M번 반복해야 하므로 O(NM)이 된다.

 

길이 N짜리 배열을 순회하고 그다음에 길이 M짜리 배열을 순회한다면, 이 경우에는 N번 반복한 후 M번 반복하므로 O(N+M)으로 표기한다.

 

문제를 보고 효율적인 풀이를 바로 떠올리기 어렵다면 문제에서 주어진 입력 조건을 이용하여 풀이의 시간 복잡도를 먼저 유추해 보는 것도 풀이를 생각해 내기에 좋은 힌트가 될 수 있다.

 

제한 시간이 1초일 때

N	유추 가능한 시간 복잡도	유추 가능한 알고리즘
10	O(N!)	순열
20	O(2N)	조합
1,000~	O(N3), O(N3 logN)	완전 탐색, 이진 탐색
10,000~	O(N logN)	정렬, 이진 탐색