검색이란 ?
검색이란 특정 데이터를 찾아내는 작업을 말합니다.
검색에 있어서 목표가 되는 데이터를 키(key)라 하고 데이터베이스에 저장된 데이터는 키와 키 이외의 데이터가 여러 조합으로 구성됩니다.
1. 선형 검색
선형검색이란 ?
선형검색은 맨 앞 또는 맨 마지막 데이터부터 차례로 살펴보면서 원하는 데이터를 찾아내는 방법입니다.
| 배 | 감 | 딸기 | 사과 | 포도 |
|---|
다음과 같은 구조의 데이터가 있을 때 앞부터 선형검색으로 사과를 찾으려면 총 4번의 시도를 통해 찾을 수 있습니다.
이때 사과를 찾는 걸린 시간과 노력을 '계산량' 이라하고 계산량은 알고리즘이 답을 찾는데 필요한 시간을 기준으로 삼습니다. 이 계산량을 O(빅오)표기법을 사용해서 나타냅니다.
일반적으로 계산량은 계산할 때 사용한 자원의 양을 말하고, 계산하는데 걸린 시간은 '시간 복잡도' 라하고, 계산하는 데 필요한 메모리의 양을 '공간 복잡도' 라고 합니다.
위 예시를 통해 선형 검색에서의 시간 복잡도는 데이터의 크기에 비례함을 알 수 있습니다.
이를 표를 통해 알아보면
| 데이터 수 | 계산량이 가장 많을 때 | 계산량이 가장 적을 때 | O 표기법 |
|---|---|---|---|
| 5 | 5 | 1 | O(5) |
| 10 | 10 | 1 | O(10) |
| n | n | 1 | O(n) |
다음과 같이 표현할 수 있습니다.
2. O 표기법 (빅오표기법)
O 표기법은 알고리즘의 최악의 실행 시간을 표기합니다.
O 표기법을 빠른 알고리즘에서 느린 알고리즘 순서로 알아보면
빠름 >>>>>>>>>>>>>>>>>>>>>>>>> 느림
O(1) > O(log n) > O(n) > O(nlog n) > O(n^2)
다음과 같습니다.
O표기법은 다음과 같은 특징을 가집니다.
1. 상수항 생략
어떤 알고리즘이 O(n+3)의 복잡도를 가지면, 상수를 생략해 O(n)으로 표현합니다.
2. 계수도 무시
어떤 알고리즘이 O(3n)의 복잡도를 가지면, 계수를 생략해 O(n)으로 표현합니다.
3. 최고차항만 표기
어떤 알고리즘이 O(3n^3+2n^2+n+1)의 복잡도를 가지면, O(n^3)으로 표현합니다.
3. 선형검색 프로그램 만들어보기
배열에서 원하는 데이터를 검색하는 프로그램을 파이썬을 통해 만들어 보겠습니다.
a = ['cat', 'dog', 'bear', 'tiger', 'lion', 'panda']
print(a.index('dog'))다음과 같이 배열 a를 만들고 dog의 index값을 출력해보면
1이 출력됨을 확인할 수 있습니다.
선형검색 방법으로 데이터를 찾는 프로그램을 만들어보면
d = [['cat', 'small', '2'], ['dog', 'small', '3'],
['bear', 'big', '600'], ['tiger', 'big', '500'],
['lion', 'big', '550'], ['panda', 'big' '400']]
for i in d:
if i[0] == 'dog':
print(i)다음과 같이 작성할 수 있습니다.
for문을 통해 d 배열을 처음부터 순차적으로 'dog'와 같은 값이 있는지 찾고 이를 찾으면 출력해주는 프로그램입니다.
