코딩 테스트에서 알고리즘을 고르는 기준이 되는 시간 복잡도 정리.
- 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘 선택
- 주어진 문제를 해결하기 위한 연산 횟수
- 표기법
- 빅-오메가(Ω): 하한(lower bound). 아무리 빨라도 이 정도는 걸린다
- 빅-세타(Θ): 상한과 하한이 같은 정확한 차수(tight bound)
- 빅-오(O): 상한(upper bound). 아무리 느려도 이보다는 빠르다
- 최선/평균/최악의 경우(case)와 표기법은 별개 개념. 보통 최악의 경우를 빅-오로 나타낸다
- 코딩 테스트에서는 worst case 고려해서 따져주기
- ex) 버블 정렬 vs 병합 정렬
- c++ 1억번 연산 = 1초 (대략)
시간 복잡도를 바탕으로 코드 로직 개선하기
작성된 코드의 비효율적인 로직을 개선하는 바탕으로도 사용가능. 시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외 O(n) ~= O(3n)
- 가장 많이
중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. (for, while..) 이중 for문 등.
Summary
- 코딩 테스트에서는
최악의 경우를 빅-오 O( )로 따진다 - 시간 복잡도 도출
- 상수 X
- 가장 많이 중첩된 반복문 기준
- 알고리즘 선택 기준
- 시간초과시 내 비효율적 코드가 어디인지 판단 기준