Ambition

728x90

수학과 컴퓨터 과학, 언어학 또는 관련 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표한한 것, 연산을 실행하기 위한 단계적 절차를 의미한다.

조금 더 정확한 의미를 따져보자면 알고리즘은 어떠한 행동을 하기 위해서 만들어진 명령어의 유한 집합이다.

컴퓨터 과학에서 말하는 알고리즘은 보통 문제를 풀기 위한 작은 진행 절차를 의미하며, 알고리즘 자체는 컴퓨터가 등장하기 이전부터 존재했던 개념이다.

주어진 배열 속에서 특정 값을 찾는 방법.

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

만약 어떤 값이 배열에 속해 있는지 찾기 위해선 배열이 정렬이 되어있는지 여부에 따라 여러 가지 방법을 사용할 수 있습니다.

다른 이름으로 순차 검색(Sequential Search) 이라고도 합니다.

데이터가 모인 집합체(배열, 링크드 리스트 등)의 인덱스를 처음부터 끝까지 하나씩 증가시키며
비교하면서 원하는 값이 맞는지 찾는 알고리즘입니다.

이진 검색은 배열의 중간 인덱스부터 탐색하기 시작하여 찾고자 하는 값과 비교하여

그보다 작은 인덱스나 큰 인덱스로 이동을 반복합니다.

반드시 데이터의 집합의 정렬되어 있어야 합니다.

데이터를 반으로 나누면서 연산하기 때문에 처리속도가 매우 빠르다는 장점을 가지고 있습니다.

위의 그림은 알고리즘을 실행하는데 걸리는 시간을 공식으로 표기한 것입니다.

여기서 O는 "on the order of"의 약자이며, "~만큼의 정도로 커지는" 것이라고 할 수 있습니다.

O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 되며 O(n/2) 또한 결국 n이 커지면 1/2는 큰 의미가 없어지므로 O(n)이라고 볼 수 있습니다.

주로 아래와 같은 Big O표기가 실행 시간을 나타내기 위해 많이 쓰입니다.

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

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

역시 아래 목록과 같은 Big Ω 표기가 사용됩니다.

[Algorithms] 검색 알고리즘