[알고리즘] 정렬 알고리즘의 실행시간

학습 목표

여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있다.

1. 실행시간 정리

1.1 실행시간의 상한

O(n^2): 선택 정렬, 버블 정렬  
O(n log n)  
O(n): 선형 검색  
O(log n): 이진 검색  
O(1)  

 

1.2 실행시간의 하한

Ω(n^2): 선택 정렬
Ω(n log n)
Ω(n): 버블 정렬
Ω(log n)
Ω(1): 선형 검색, 이진 검색

 

#이 파트는 이해 못해서 문제 다 틀렸다. 구글링 해서 자료 보강하고 추가 해놓을 것.