Big-O 표기법 활용하기

네가 그렇게 정렬을 잘 해?!

 

알고리즘 과목을 처음 배워도, 코딩테스트를 처음 시작하려고 해도 꼭 나오는 개념이 있다.

바로 시간 복잡도를 표현할 수 있는 Big-O 표기법이다.

문제만 풀 줄 알면 됐지 하고 넘어간다면, 시간 초과 오류와 마주칠지도 모르겠다.

 

이론은 이해하겠는데,
대체 코딩테스트 문제를 풀 때 어떻게 활용하라는 거야?

 

 

 

시간 복잡도란?

 

알고리즘의 연산 횟수, 즉 성능을 수학적으로 표현해주는 표기법이다.

일반적으로 1초에 1억 번의 연산을 수행한다고 가정한다.

Big-O 시간 복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 한다.

(Big-Ω는 최선일 때, Big-Θ는 보통일 때를 나타낸다.)

 

실제 러닝타임보다는 알고리즘의 성능을 예측하는 것이 목표이기 때문에 상수는 고려하지 않는다.

반복문이 여러 개 있어도 가장 많이 중첩된 반복문을 기준으로 시간복잡도를 계산한다.

 

Big-O 표기법의 종류

 

O(1)

• 입력한 데이터에 상관없이 언제나 일정한 시간이 소요된다. ex) 상수

O(n)

• 데이터와 시간이 같은 비율로 증가한다. ex) 반복문

O(n^2)

• ex) 이중 반복문, 삽입 정렬, 버블 정렬, 선택 정렬

O(2^n)

• ex) 피보나치 수열 (재귀함수)

O(log(n))

• 한 번 처리가 진행될 때마다 검색해야 하는 데이터가 절반이 된다. ex) 이진 탐색 

O(sqrt(n))

 

 

Big-O 표기법의 크기 비교

 

O(1) < O(log(n)) < O(n) < O(n log(n)) < O(N^2) < O(2^n)

 

 

활용법
(백준 2750. 수 정렬하기 / 시간 제한 2초)

 

버블 정렬의 시간 복잡도가 O(n^2), 병합 정렬이 O(n log(n))임을 알고 있다고 하자.

 

< 문제 >

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

 

< 입력 >

1번째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다. 수는 중복되지 않는다.

 

< 출력 >

// 예제 입력
5
5
2
3
4
1

// 예제 출력
5
1
2
3
4
5

 

 

< 풀이 >

시간 제한이 2초이므로 총 2억 번 이하의 연산 횟수로 문제를 해결해야 한다.
(연산 횟수는 1초에 1억 번이라고 가정한다.)

 

* 연산 횟수 계산 방법은 알고리즘 시간 복잡도 * 데이터의 크기이다.

• 버블 정렬
  = n^2 = (1,000,000)^2 = 1,000,000,000,000
  > 200,000,000 → 부적합 알고리즘

• 병합 정렬
  = n logn = 1,000,000 * log(1,000,000) = 약 20,000,000
  < 200,000,000 → 적합 알고리즘

 

 

추가로, 자주 사용하는 정렬 메서드의 시간 복잡도에 대해서도 찾아보았다.

정렬 메서드	시간 복잡도
Arrays.sort()	O(n^2)
Collections.sort()	O(n log(n))