CH 01. 알고리즘 소개
- 알고리즘 : 어떤 일을 하기 위한 명령의 집합
- 이진 탐색 (binary search)
리스트의 원소가 정렬되어있어야만 사용 가능
리스트에 원하는 원소가 존재하면 그 원소의 위치를 반환, 아니면 null 반환
n개의 원소를 가진 리스트에서 최대 log_2_n번 만에 답 찾기 가능
# 이진 탐색 함수
def binary_search(list, item):
low = 0
high = len(list)-1
while low <= high:
mid = (low + high) // 2
guess = list[mid]
if guess == item:
return mid
if guess > item:
high = mid - 1
else:
low = mid + 1
return None
## 테스트
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3))
print(binary_search(my_list, -1))
- 실행 시간
> 선형 시간 : 추측해야할 최대 횟수 = 리스트의 길이 (순차적으로 확인하는 경우)
> 이진 시간 : 추측해야할 최대 횟수 = log_2_n번=로그 시간 (이진 탐색 시)
- 빅오 표기법 : 알고리즘이 얼마나 빠른지 표시하는 방법, 괄호 안에는 연산 횟수 기재
1) 선형 시간 (빅오 표기법 기준) : O(n)
2) 이진 시간 (빅오 표기법 기준) : O(log n)
3) O(n*log n) : 퀵 정렬과 같이 빠른 정렬 알고리즘
4) O(n^2) : 선택 정렬과 같이 느린 정렬 알고리즘
5) O(n!) : 정말 느린 알고리즘
ex. 종이에 16개의 네모칸 만들기
알고리즘 1. 네모 하나씩 그려서 총 16개의 네모 그리기 > O(16) 시간
알고리즘 2. 종이를 4번 접어서 16개의 네모칸 접기 > O(log 16) 시간
