선형 검색, 이진 검색의 시간 복잡도

Big-O 표기법에 따른 결론부터 말하면, 선형 검색은 O(n), 이진 검색은 O(logn)이다.

 

선형 검색의 시간 복잡도 따져보기

def linear_search(array, elem):
    for i, e in enumerate(array):		#1
        if elem == e:				#2
            return i				#3
    return -1					#4

• #1, 시간 복잡도 O(n), 실행 횟수 n/2 (평균적으로 n/2개에 대해 수행, n에 비례하여 시간복잡도가 O(n)이 됨)
• #2, 시간 복잡도 O(n), 실행 횟수 n/2
• #3, 시간 복잡도 O(1), 실행 횟수 1
• #4, 시간 복잡도 O(1), 실행 횟수 1

Big-O 표기법은 최댓값을 채택하므로, 선형 검색의 시간복잡도는 O(n)이다.

 

이진 검색의 시간 복잡도 따져보기

def binary_search(array, elem):
    # sort
    array.sort()

    lower_bound = 0					#1
    upper_bound = len(array)-1				#2

    while lower_bound < upper_bound:			#3
        index = (lower_bound+upper_bound)//2		#4
        if array[index] == elem:			#5
            return index 				#6
        elif array[index] > elem:			#7
            upper_bound = index				#8
        else:
            lower_bound = index				#9
    return -1						#10

• #1, #2, #6, #10, 시간 복잡도 O(1), 실행 횟수 1
• #3, #4, #5, #7, #8, #9, 시간 복잡도 O(logn), 실행 횟수 logn (데이터를 절반씩 줄여나가서 logn 회)

Big-O 표기법은 최댓값을 채택하므로, 이진 검색의 시간복잡도는 O(logn)이다. 단, 이진 검색의 전제 조건은 정렬된 것으로, 정렬이 안되어 있는 배열에 대하여 정렬을 수행하는 시간은 또 다른 문제가 된다.

 

참고 자료 및 소스 코드

선형 검색 및 이진 검색 코드: https://github.com/twndus/algorithm-note/tree/main/algorithm/search

참고 자료:  Do it! 자료구조와 함께 배우는 알고리즘 입문