들어가기 전에
지금까지의 강의에서 정렬 알고리즘이나 검색 알고리즘을 학습하면서 그 실행 시간의 상한과 하한도 함께 배워 보았습니다. 이번 강의에서는 각 알고리즘들의 실행 시간을 비교해보고, 그 시간을 좀 더 단축시키는 방법이 있을지 알아보겠습니다.
학습 목표
여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있습니다.
핵심 단어
- Big O
- Big Ω
여태까지 배운 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간은 각각 어떻게 되는지 정리해 보겠습니다.
실행시간의 상한
- O(n^2): 선택 정렬, 버블 정렬
- O(n log n)
- O(n): 선형 검색
- O(log n): 이진 검색
- O(1)
실행시간의 하한
- Ω(n^2): 선택 정렬, 버블 정렬
- Ω(n log n)
- Ω(n)
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
여기서 버블 정렬을 좀 더 잘 할 수 있는 방법을 알아보겠습니다.
만약 정렬이 모두 되어 있는 숫자 리스트가 주어진다면 어떨까요?
원래 의사 코드는 아래와 같습니다.
Repeat n–1 times
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
여기서 안쪽 루프에서 만약 교환이 하나도 일어나지 않는다면 이미 정렬이 잘 되어 있는 상황일 것입니다.
따라서 바깥쪽 루프를 ‘교환이 일어나지 않을때’까지만 수행하도록 다음과 같이 바꿀 수 있습니다.
Repeat until no swaps
For i from 0 to n–2
If i'th and i+1'th elements out of order
Swap them
따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 됩니다.
상황에 따라서는 선택 정렬보다 더 빠른 방법이 되는 것이죠.
실행시간의 하한
- Ω(n^2): 선택 정렬
- Ω(n log n)
- Ω(n): 버블 정렬
- Ω(log n)
- Ω(1): 선형 검색, 이진 검색
생각해보기
선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?
나의 생각 : 최솟값을 찾아야하기 때문에 안될 것 같다.
출처 : https://www.boostcourse.org/cs112/lecture/119024?isDesc=false 네이버커넥트재단