알고리즘 상한과 하한

알고리즘 상한은 O로 표기하며 아래 표에서 시간이 오래걸리는 순으로 나열되어있다.

알고리즘 하한은 Ω로 표기하며 아래 표에서 시간이 오래걸리는 순으로 나열되어있다.

1. 선형검색 (Linear search)

선형검색은 전화번호부에서 사람이름을 한장한장 넘기면서 찾는 방법이다.
최선(Ω)의 경우 1번만에 찾을수있지만 최악(O)의 경우 n번만에 찾을 수 있다.

2. 이진검색 (Binary search)

이진검색은 전화번호부에서 사람이름을 찾기 위해,
책의 중간지점부터 시작하여 중간지점의 이름을 확인 한 후, 필요없는 절반은 버려가는 방식으로 찾아가는 방법이다.
최선(Ω)의 경우 1번만에 찾을수있지만 최악(O)의 경우 log n번만에 찾을 수 있다.

3. 선택정렬 (Selection sort)

선택정렬은 가장 작은 숫자를 찾아서 가장 왼쪽에있는 숫자와 교체하는 것을 반복하여 정렬하는 방법이다.
정렬하다보면 가장 작은수가 왼쪽부터 쌓이는 과정이 발생한다.
최선(Ω)의 경우 n2 번만에 정렬할수있고, 최악(O)의 경우에도 n2번만에 찾을 수 있다.

4. 버블정렬 (Bubble sort)

버블정렬은 인접한 두 숫자를 비교하여 더 작은 수를 교체하여 정렬하는 방법이다.
정렬하다보면 가장 큰수가 오른쪽부터 쌓이는 과정이 발생한다.
최선(Ω)의 경우 n번만에 정렬할수있고, 최악(O)의 경우 n2번만에 찾을 수 있다.

5. 병합정렬 (Merge sort)

병합정렬은 배열을 이용하여 정렬하는 방법이다.
먼저, 수들을 반절로 지속적으로 나눈 후, 가장 왼쪽의 두 수를 비교하여 작은수부터 왼쪽으로 정렬한다.
다음으로, 그 다음 두가지 숫자중 작은 수를 왼쪽으로 정렬한다.
그리고 2개, 2개의 수중 가장 작은 수부터 왼쪽으로 정렬한다.
정렬이 다되었으면 오른쪽의 4개도 같은 방법으로 정렬한다.
다음으로 4개, 4개의 비교로 8개를 정렬한다.
이런식으로 반복하여 n개 까지 정렬한다.
최선(Ω)의 경우 nlog n번만에 정렬할수있고, 최악(O)의 경우에도 nlog n번만에 찾을 수 있다.