유형
- 빅 오메가: 최선일 때의 연산 횟수를 나타낸 표기법
- 빅 세타: 보통일 때의 연산 횟수를 나타낸 표기법
- 빅 오: 최악일 때의 연산 횟수를 나타낸 표기법
수 정렬하기 예시
항상 최악의 경우를 생각해서 생각을 한다. 버블 정렬과 병합 정렬이 있을 경우에 시간 복잡도를 한번 생각해본다.
- 버블 정렬: O(n^2)
- 병합 정렬: O(nlogn)
문제에서 주어진 시간 제한과 데이터 크기를 바탕으로 어떤 정렬 알고리즘을 사용해야 할 것인지를 판단해야한다.
예시로 문제에 시간 제한 2초에 연산 횟수 4,000만 번 안에 원하는 답을 구해야 한다면, n = 1,000,000인 경우에 버블정렬은 1조 번의 연산 횟수가 필요하므로 적합한 알고리즘이 아니라고 판단할 수 있다.