python - 시간복잡도(Time Complexity)와 예제

시간복잡도(Time Complexity)

시간복잡도는 알고리즘의 실행 시간이 입력 크기(input size, n)에 따라 어떻게 변화하는지를 평가하는 척도입니다.
빅오 표기법(Big-O Notation)을 사용해 최악의 경우를 기준으로 표현하며, 알고리즘의 효율성을 비교하는 데 활용됩니다.

---

1. 빅오 표기법(Big-O Notation)

입력 크기 증가에 따른 실행 시간의 상한(최악의 경우)을 수학적으로 간단히 표현합니다.

빅오 표기법	설명	예시
O(1)	상수 시간 (입력 크기에 무관)	배열 첫 요소 접근, 변수 선언
O(log n)	로그 시간 (입력 크기의 로그에 비례)	이진 탐색
O(n)	선형 시간 (입력 크기에 비례)	배열 순회, 선형 탐색
O(n log n)	로그 선형 시간	퀵 정렬, 병합 정렬
O(n²)	이차 시간 (중첩 반복문)	버블 정렬, 선택 정렬
O(n³)	삼차 시간 (3중 반복문)	플로이드-워셜 알고리즘
O(2ⁿ)	지수 시간 (매우 비효율적)	피보나치 재귀 (메모이제이션 없이)
O(n!)	팩토리얼 시간 (모든 순열 계산)	외판원 문제(브루트포스)

---

2. 시간복잡도 예제

(1) O(1): 상수 시간복잡도
입력 크기와 무관하게 실행 시간이 일정합니다.

# 배열의 첫 번째 요소 접근
arr = [1, 2, 3, 4, 5]
print(arr[0])  # O(1)

 

(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

arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7))  # O(log n)

 

(3) O(n): 선형 시간복잡도
입력 크기에 비례해 실행 시간이 증가합니다.

# 배열 순회
arr = [1, 2, 3, 4, 5]
for num in arr:
    print(num)  # O(n)

 

 

(4) O(n log n): 로그 선형 시간복잡도
대표적으로 병합 정렬, 퀵 정렬 - 정렬 알고리즘에서 나타납니다.

# 병합 정렬
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left or right)
    return result

arr = [5, 3, 8, 4, 2]
print(merge_sort(arr))  # O(n log n)

 

(5) O(n²): 이차 시간복잡도
이중 반복문 사용 시 발생하며, 대표적으로 버블 정렬이 있습니다.

# 버블 정렬
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]
    return arr

arr = [5, 3, 8, 4, 2]
print(bubble_sort(arr))  # O(n^2)

---

3. 시간복잡도의 비교

시간복잡도 증가에 따른 실행 시간 변화
입력 크기(nn)에 따른 실행 시간 증가율:

nn	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2ⁿ)
10	1	3	10	30	100	1,024
100	1	6	100	600	10,000	1.27×10³0
1,000	1	9	1,000	9,000	1×10⁶	1.07×10³0¹

---

4. 시간복잡도 분석 방법

(1) 입력 크기 파악

• 입력 크기(nn)가 무엇인지 확인합니다.
• 예: 배열의 길이, 그래프의 노드 개수.

(2) 연산 횟수 계산

• 반복문이나 재귀 호출의 실행 횟수를 분석합니다.
• 예: 중첩 반복문 → O(n²)

(3) 가장 빠르게 증가하는 항만 남기기

• 상수 및 작은 항 제거.
• 예: 5n² + 3n + 2 → O(n²)

(4) 빅오 표기

• 최악의 경우를 기준으로 작성합니다.

---

5. 시간복잡도와 공간복잡도

• 시간복잡도(Time Complexity): 알고리즘의 실행 시간을 평가.
• 공간복잡도(Space Complexity): 알고리즘이 사용하는 메모리 공간 평가.
• 두 가지를 균형 있게 고려하여 최적의 알고리즘 설계.

---

6. 실습 문제

문제 1: 최대값 찾기 (시간복잡도: O(n))

def find_max(arr):
    max_value = arr[0]
    for num in arr:
        if num > max_value:
            max_value = num
    return max_value

arr = [3, 1, 4, 1, 5, 9]
print(find_max(arr))  # 출력: 9

 

문제 2: 이중 반복문 예제 (시간복잡도: O(n²))

arr = [1, 2, 3]
for i in range(len(arr)):
    for j in range(len(arr)):
        print(arr[i] + arr[j])