시간복잡도
- 주어진 문제를 해결하기 위한 연산 횟수
- 100,000,000의 연산 = 1초
시간복잡도의 유형
- 빅-오메가(Ω(n)) : 최고의 경우일 때 연산횟수를 나타낸 표기법
- 빅-세타(Θ(n)) : 보통의 경우일 때 연산횟수를 나타낸 표기법
- 빅-오(O(n)) : 최악의 경우일 때 연산횟수를 나타낸 표기법
최악의 경우를 염두에 두는 빅-오 표기법을 기준으로 수행시간 계산하기!
빅-오 표기법의 시간복잡도
- O(logn) - O(n) - O(nlogn) - O(n^2) - O(2^n) - O(n!)
시간복잡도 활용 예제(백준 2750번) 링크
-
N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 완성하시오
-
입력 : 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
-
출력 : 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
| 시간제한 | 메모리제한 |
|---|---|
| 2초 | 128MB |
Solution
- 버블정렬 시간복잡도 : O(n^2) => 약 1,000,000,000,000번 연산
- 병합정렬 시간복잡도 : O(nlogn) => 약 20,000,000
- 연산 횟수 = 10,000,000*2 => 20,000 => 병합정렬 사용하기
주의할 점
1. 상수는 시간복잡도 계산 X
2. 가장 많이 중첩된 반복문의 수행횟수를 기준으로 계산
