CS이론/알고리즘
시간복잡도
유로파니
2020. 7. 5. 21:14
● Big-O 표기법(빅오 표기법) - 실행 시간의 상한(최대시간), Worst
- O(n^2): 선택 정렬, 버블 정렬, 삽입 정렬
- O(n log n) : 병합 정렬
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1)
● Big-Ω 표기법(빅오메가 표기법) - 실행 시간의 하한(최소시간), Best
- Ω(n^2): 선택 정렬, 버블 정렬
- Ω(n log n) : 병합 정렬
- Ω(n) : 삽입 정렬
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
