알고리즘 | 정렬 알고리즘의 실행시간

✔ 학습목표

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

2. 조건문을 사용해 좀 더 효율적인 알고리즘을 만들 수 있다.

 

알고리즘의 실행 시간

이제껏 배운 선형 검색(Linear search), 이진 검색(Binary search), 버블 정렬(Bubble sort), 선택 정렬(Selection sort)의 실행시간(시간 복잡도)은 각각 어떻게 되는지 정리해보자.

 

상한은 다음과 같다.

 

	O(1)	O(log n)	O(n)	O(n log n)	O(n^2)
Linear search			o
Binary search		o
Bubble sort					o
Selection sort					o

 

하한은 다음과 같다.

 

	Ω(1)	Ω(log n)	Ω(n)	Ω(n log n)	Ω(n^2)
Linear search	o
Binary search	o
Bubble sort					o
Selection sort					o

 

알고리즘의 시간 단축

알고리즘의 실행 시간은 항상 같을까? 앞서 배운 버블 정렬을 예로 들어보자. 버블 정렬은 정렬이 끝난 뒤에도 정해진 비교를 진행하는 단점이 있었다. 의사 코드는 다음과 같다.

 

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

 

의사 코드에 Until no swaps이라는 조건이 추가되었다. 따라서 최종적으로 버블 정렬의 하한은 Ω(n)이 된다(정렬이 끝나있는 상태에서 버블정렬). 상황에 따라 선택 정렬보다 빠른 방법이 되는 것이다.

 

* 선택정렬의 경우 배열의 모든 값을 살펴봐야 하기 때문에 실행 시간의 하한을 단축할 수 없다.

 

 

---

 

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

모두를 위한 컴퓨터 과학 (CS50 2019)