- 버블 정렬의 시간복잡도 : O(n^2)
- 병합 정렬의 시간복잡도 : O(nlogn)
백준 2750. 수 정렬하기
N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오
1번째 줄에 수의 개수 N(1 <= N <= 1,000,000), 2번째 줄부터는 N개의 줄에 숫자가 주어진다.
이 수는 절댓값이 1,000,000보다 작거나 같은 정수다. 수는 중복되지 않는다.
시간제한이 2초 = 2억번 이하의 연산횟수
- 연산 횟수는 1초에 1억번 연산하는 것을 기준
- 시간복잡도는 최악일 떄, 즉 데이터의 크기가 가장 클 때가 기준
연산 횟수 계산 방법
- 연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기
알고리즘 적합성 평가
- 버블 정렬 = (1,000,000)^2 = 1,000,000,000,000 > 200,000,000 -> 부적합
- 병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 -> 적합
시간 복잡도 도출 기준
1) 상수는 시간 복잡도 계산에서 제외
2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준
Ex)
for문이 N번 도는 코드 A
For문이 N번 도는 코드가 세개 있는 B
연산 횟수는 3배 차이가 나지만 상수를 무시하므로 두 코드 모두 시간복잡도는 O(n)
N번 도는 for문이 중첩되어 있는 경우
시간복잡도는 O(n^2)
