[자료구조 멘토링] 시간 복잡도

1. 시간 복잡도란?

시간 복잡도란 알고리즘이 실행하는 데, 걸리는 시간을 입력크기에 대한 함수로 나타내는 것이다. 

즉, 입력 크기가 증가할때 알고리즘의 실행 시간은 어떻게 변하는 지 분석하는 것이다.

 

빅오 표기법을 사용하여 최악의 경우를 기준으로 나타내는 것이 일반적이다.

 

 

1-1. 상수 시간 - O(1)

입력 크기와 상관없이 항상 일정한 시간이 걸리는 경우

예시) 배열의 첫 번째 요소를 출력하는 경우

def get_first_element(arr):
    return arr[0]  # 항상 한 번만 실행됨 → O(1)

 

1-2. 선형 시간 - O(N)

입력 크기가 n이면 실행 횟수도 n번 증가하는 경우

예시) 리스트의 모든 요소를 출력하는 경우

def print_all_elements(arr):
    for elem in arr:
        print(elem)  # n개의 요소에 대해 반복 실행 → O(n)

 

1-3. 로그 시간 - 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  # O(log n)

 

1-4. 제곱 시간 - O(n**2)

입력 크기가 커질수록 실행 시간이 제곱으로 증가하는 경우

예시) 버블 정렬

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # O(n^2)