CS50 2019 강의를 듣고 내용을 정리한 시리즈 글입니다.
학습목표
여러 정렬 알고리즘과 검색 알고리즘의 실행 시간을 Big O와 Big Ω로 정의할 수 있습니다.
핵심 단어
- Big O
- Big Ω
강의 내용
1. 선형 검색, 이진 검색, 버블 정렬, 선택 정렬의 실행시간
선형 검색: O(n), Ω(1)
이진 검색: O(log n), Ω(1)
버블 정렬: O(n^2), Ω(n^2)
선택 정렬: O(n^2), Ω(n^2)
2. 버블 정렬 실행시간 단축
이미 정렬이 완료된 배열이 주어진다는 가정 하에 버블 정렬의 실행시간을 단축시켜보자.
def bubble_sort(array):
for i in range(len(array)):
swap = False
for j in range(0, len(array) - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
swap = True
if swap == False:
break
return array기존 코드에 swap 변수를 boolean으로 추가해 교환이 이루어지지 않을 경우(정렬이 완료된 경우) 바로 코드를 종료하도록 만들었다.
이렇게 수정한 버블 정렬의 Big Ω는 Ω(n)이 된다.
1번 내용을 다시 정리해보면
선형 검색: O(n), Ω(1)
이진 검색: O(log n), Ω(1)
버블 정렬: O(n^2), Ω(n)
선택 정렬: O(n^2), Ω(n^2)
상황에 따라 버블 정렬이 선택 정렬보다 더 빠른 방법이 될 수 있음을 알 수 있다.
생각해보기
선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?
선택 정렬의 경우 정렬된 배열의 경우에도 최소값을 비교하는 과정을 반복하기 때문에 끝까지 확인하기 전까지는 종료할 수 없다.
