CS50 4. 알고리즘(1) - 검색 알고리즘, 알고리즘 표기법

배열은 한 자료형의 여러 값들이 메모리상에 모여 있는 구조. 컴퓨터는 이 값들에 접근할 때 배열의 인덱스 하나하나를 접근한다.

만약 어떤 값이 배열 안에 속해 있는지를 찾아 보기 위해서는 배열이 정렬되어 있는지 여부에 따라 아래와 같은 방법을 사용할 수 있다.

 

 

선형 검색

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

아래 의사코드와 같이 나타낼 수 있다.

 

이진 검색

만약 배열이 정렬되어 있다면, 배열 중간 인덱스부터 시작하여 찾고자 하는 값과 비교하며 그보다 작은(작은 값이 저장되어 있는) 인덱스 또는 큰 (큰 값이 저장되어 있는) 인덱스로 이동을 반복하면 된다.

아래 의사코드와 같이 나타낼 수 있다.

 

알고리즘 표기법

알고리즘을 실행하는데 걸리는 시간

 

위와 같은 그림을 공식으로 표기한 것이 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 Ω는 알고리즘 실행 시간의 하한을 나타낸다.

예를 들어 선형 검색에서는 n개의 항목이 있을때 최대 n번의 검색을 해야 하므로 상한이 O(n)이 되지만 운이 좋다면 한 번만에 검색을 끝낼수도 있으므로 하한은 Ω(1)이 된다.

 

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

• Ω(n^2)
• Ω(n log n)
• Ω(n) - 배열 안에 존재하는 값의 개수 세기
• Ω(log n)
• Ω(1) - 선형 검색, 이진 검색

※ 실행시간의 상한이 낮은 알고리즘이 더 좋을까, 하한이 낮은 알고리즘이 더 좋을까?

하한선이 낮은경우는 특정상황에 의존하여 결과가 나오길 기대해야 하지만 상한선이 낮은경우는 평균적으로 실행시간이 줄어드는것을 의미하기 때문에 실행시간의 상한선이 낮은 알고리즘이 더 좋다. 최대치를 알고 코드를 작성하는것이 효율적으로 코드를 작성할 수 있다고 생각