[알고리즘] 시간 복잡도와 정렬 알고리즘

실행시간의 상한

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

실행시간의 하한

• Ω(n^2): 선택 정렬
• Ω(n log n): 병합 정렬
• Ω(n): 버블 정렬-> 정렬이 모두 되어 있는 경우
• Ω(log n)
• Ω(1): 선형 검색, 이진 검색

 

1. 시간 복잡도가 O(n^2)인 정렬 알고리즘

삽입정렬, 거품 정렬(버블 정렬), 선택 정렬

2. 시간 복잡도가 O(nlogn)인 정렬 알고리즘

병합 정렬(merge sort), 힙 정렬

3. 시간 복잡도가 O(n)인 정렬 알고리즘

counting 정렬