c언어-알고리즘

검색 알고리즘

 

선형 검색

배열의 인덱스를 처음부터 끝까지 하나씩 증가시키면서 방문하여 그 값이 속하는지 검사한다.

For i from 0 to n–1

    If i'th element is 50

        Return true

Return false

이진 검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 

그보다 작은 (작은 값이 저장되어 있는) 인덱스 또는 큰(큰 값이 저장되어 있는) 인덱스로 

이동을 반복하면 된다.

If no items

    Return false

If middle item is 50

    Return true

Else if 50 < middle item

    Search left half

Else if 50 > middle item

    Search right half

 

 

알고리즘 표기법

 

Big O 표기법

여기서 O는 on the order of의 약자로 쉽게 생각하면 "~만큼의 정도로 커지는 것" 이라고 볼 수 있다.

O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 된다.

O(n/2)도 결국 n이 매우 커지면 1/2은 큰 의미가 없어지므로 O(n) 이라고 볼 수 있다.

 

주로 아래 목록과 같은 big O 표기가 실행 시간을 나타내기 위해 많이 사용된다.

실행 시간의 상한

 

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

 

Big O가 알고리즘 실행 시간의 상한을 나타낸 것이라면, 반대로 Big Ω는 알고리즘 실행 시간의 하한을 나타내는 것이다.

아래 목록과 같은 Big Ω 표기가 많이 사용된다.

실행 시간의 하한

Ω(n^2)
Ω(n log n)
Ω(n) -  버블 정렬
Ω(log n)
Ω(1) - 선형 검색, 이진 검색

 

 

 

선형 검색

자료를 검색할 때 사용되는 다양한 알고리즘 중 하나.

선형 검색은 원하는 원소가 발견될 때까지 처음부터 마지막 자료까지 차례대로 검색한다.

선형 검색 알고리즘은 정확하지만 아주 효율적이지 못하다.

리스트의 길이가 n개면 처음부터 마지막 n까지 실행되기 때문.

 

선형 검색은 자료가 정렬되어 있지 않거나 그 어떤 정보도 없어서 하나씩 찾아야 하는 경우에 유용하다

 

버블 정렬

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 효율적이다.

정렬 알고리즘 중 하나는 버블 정렬이 있다.

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말한다.

버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다.

 

예를 들어 

5 6 2 9 1 4 를 정렬할 때 

5 6 2 9 1 4

5 2 6 9 1 4 (교환)

5 2 6 1 9 4 (교환)

5 2 6 1 4 9 (교환)

식으로 진행하면

1 2 4 5 6 9 가 최종적으로 정렬된다.

 

선택 정렬 

보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있다.

정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치

(혹은 가장 마지막 위치)의 수 와 교환해주는 방식의 정렬.

 

선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가한다.

 

예를 들어

5 6 2 9 1 4 를 정렬할 때

가장 작은 값인 1이 맨 앞에 있어야 하므로 5와 교환한다

1 6 2 9 5 4

그 다음 두 번째로 작은 값인 2와 6을 교환한다

1 2 6 9 5 4 

이 과정을 반복하면

1 2 4 5 6 9 가 최종적으로 정렬된다.

 

 

병합 정렬

전화번호부의 분할 정복 탐색처럼 데이터를 반으로 나누어간다는 것과 같은 공통점이 있는 병합정렬(합병 정렬))이다.

병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다.

 

예를 들어

6 5 9 2 1 4 3 8를 반으로 나눈다

6 5 9 2ㅣ1 4 3 8  첫번째를 다시 반으로 나눈다

6 5ㅣ9 2ㅣ1 4 3 8 작은 숫자가 먼저 온다

5 6ㅣ2 9ㅣ1 4 3 8 

이제 5 6 과 2 9를 병합한다

2 5 6 9 ㅣ 1 4 3 8 오른쪽을 처리한다.

 

최종적으로

1 2 3 4 5 6 8 9 가 된다.

 

병합 정렬 실행 시간의 상한은 O(n log n)이다.

각 반으로 나눈 부분들을 다시 정렬해서 병합하는 데 각각 O(n)의 시간이 걸리기 때문

 

실행 시간의 하한도 Ω(n log n)이다.

숫자들이 이미 정렬되었는지 여부에 관계 없이 나누고 병합하는 과정이 필요하기 때문