[CS] 알고리즘의 복잡도 (시간 복잡도)

알고리즘의 복잡도는 알고리즘의 성능을 평가하는 중요한 척도 중 하나이다. 이 글에서는 시간 복잡도와 공간 복잡도 중 시간 복잡도에 대해서만 간단히 정리한다.

 

시간 복잡도

• 알고리즘이 실행되는 데 걸리는 시간
• Big O 표기법을 사용하여 표현 ex) O(n), O(log n), O(n²) 등.
• 입력 크기에 따른 연산 횟수의 증가율을 나타냄

 

예시

O(1) - 상수 시간 복잡도: 연산 횟수가 입력 크기와 관계없이 일정한 경우

def get_first_element(arr):
    return arr[0] if arr else None

# 사용 예시
print(get_first_element([1, 2, 3, 4, 5]))  # 출력: 1

 

배열의 크기와 관계 없이 첫 번째 원소를 반환하는 함수이므로 일정하다.

 

O(n) - 선형 시간 복잡도: 연산 횟수가 입력 크기에 비례하여 증가하는 경우

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

# 사용 예시
print(linear_search([1, 3, 5, 7, 9], 5))  # 출력: 2

선형 탐색의 예시로 처음부터 하나씩 탐색하는 방식이므로 입력 크기에 비례해 증가한다.

 

O(log n) - 로그 시간 복잡도: 연산 횟수가 입력 크기의 로그에 비례하여 증가하는 경우

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# 사용 예시
print(binary_search([1, 3, 5, 7, 9], 7))  # 출력: 3

이진 탐색의 예시로, 검색 때 마다 범위를 반으로 줄이므로 O(log n)의 복잡도를 가진다.

 

O(n²) - 이차 시간 복잡도: 연산 횟수가 입력 크기의 제곱에 비례하여 증가하는 경우

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# 사용 예시
print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))  # 출력: [11, 12, 22, 25, 34, 64, 90]

이중 반복문을 사용하는 버블 정렬의 예시로, 입력 크기의 제곱에 비례한 시간이 소요된다.