서론

알고리즘에 대한 성능평가에서 공간 복잡도보다 중요한 부분을 차지하는 것이 시간 복잡도이다. 특히 PS에서 중요하게 다루어진다. 이번에는 시간 복잡도에 대해 간단히 이야기해보고자 한다.

시간 복잡도란?

시간 복잡도란 구현한 알고리즘이 입력의 크기에 따라 수행하는 기본 연산의 횟수를 분석하여, 알고리즘의 실행 시간이 얼마나 입력 크기에 의존하는 지를 나타내는 개념이다. 일반적으로 시간 복잡도를 표현할 때 Big O 표현법을 사용한다. Big O 표기법은 알고리즘의 실행 시간이 입력 값에 영향을 받는 상한값을 나타내며, 공식적인 표현은 다음과 같다.

$fn) = O(g(n))$에 대하여
$f(n) \le c*g(n)$를 만족한다.

시간 복잡도를 계산하는 방법

간단한 코드들로 예시를 들어보도록 하겠다.

def linear_search(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

위의 선형탐색 코드는 배열의 크기를 n이라고 하였을 때, 기본연산(target을 찾기 위해 이루어지는 연산)은 최악의 경우 모든 요소를 탐색하여 n번 반복된다. 이때 n은 c * n보다 작으므로 시간 복잡도는 O(n)이다.

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return False

위의 이진탐색 코드에서도 마찬가지로 배열의 크기를 n이라고 하였을 때, 기본연산(target을 찾기 위해 이루어지는 연산)은 최악의 경우 log(n)번 반복된다.(while을 통해 크기를 절반씩 줄여나가기 때문에) 이때 log(n)은 c * log(n)보다 작으므로 시간복잡도는 O(log(n))이다.