binary search, 빅오표기법

<시간복잡도>

단순탐색 O(n) (선형시간)

이진탐색 O(logn) (로그시간)

<binary_search>

list는 정렬된 배열

# -*- coding: cp949 -*-

def binary_search(list, item):

low = 0

high = len(list)-1

while low <= high:

mid = (low+high) / 2 #파이썬2에서는 (low+high)가 짝수가 아닐 경우 자동으로 mid 값을 정수로 내림

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) #1

print binary_search(my_list, 7) #3

print binary_search(my_list, -1) #None

<빅오 실행 시간 빠른 것부터 느린 것까지>

알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지로 측정

O(log n) < O(n) < O(n*log n) < O(n²) < O(n³) < O(2ⁿ)  < O(n!)