[CS 기초 #11] 복잡도 분석: Big-O 표기법 완벽 마스터
[CS 기초 #11] 복잡도 분석: Big-O 표기법 완벽 마스터
알고리즘의 성능을 예측하는 방법! Big-O 표기법을 알면 코드가 느려지기 전에 미리 알 수 있습니다. 최적화와 면접의 필수 지식입니다.
🎯 이 글을 읽고 나면
- Big-O 표기법이 무엇인지 정확히 설명할 수 있습니다
- O(1), O(n), O(log n), O(n²) 등의 차이를 이해합니다
- 코드를 보고 시간 복잡도를 계산할 수 있습니다
- 공간 복잡도와 시간 복잡도를 구분할 수 있습니다
- 상황에 맞는 최적의 알고리즘을 선택할 수 있습니다
📚 사전 지식
💡 핵심 개념 미리보기
Big-O 표기법은 알고리즘이 데이터가 많아질 때 얼마나 느려지는지를 나타냅니다. O(1)은 데이터가 아무리 많아도 속도가 똑같고, O(n)은 데이터가 2배면 2배 느려지며, O(n²)은 데이터가 2배면 4배 느려집니다. 이를 알면 100만 개 데이터에서도 빠른 코드를 작성할 수 있습니다!
📈 들어가며: 왜 복잡도 분석이 중요한가?
“이 코드가 더 빠를까, 저 코드가 더 빠를까?” 개발자라면 누구나 하는 고민입니다. 하지만 실행 시간을 측정하는 것만으로는 충분하지 않습니다!
오늘은 알고리즘의 효율성을 객관적으로 평가하는 복잡도 분석과 Big-O 표기법을 완벽하게 마스터해보겠습니다. 이 지식은 코드 최적화와 기술 면접의 필수 요소입니다!
🎯 복잡도 분석이란?
복잡도 분석은 알고리즘의 성능을 예측하는 방법입니다. 입력 크기가 커질수록 실행 시간이나 메모리 사용량이 어떻게 변하는지 분석합니다.
graph LR
subgraph "복잡도 종류"
TC[시간 복잡도<br/>Time Complexity]
SC[공간 복잡도<br/>Space Complexity]
end
subgraph "분석 케이스"
BC[최선 Best Case]
AC[평균 Average Case]
WC[최악 Worst Case]
end
TC --> BC
TC --> AC
TC --> WC
SC --> BC
SC --> AC
SC --> WC
왜 실행 시간 측정만으로는 부족한가?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
import time
import random
def why_big_o_matters():
"""실행 시간의 한계 시연"""
# 두 가지 검색 알고리즘
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
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
# 작은 입력에서 테스트
small_arr = sorted([random.randint(1, 100) for _ in range(10)])
target = small_arr[5]
# 선형 검색
start = time.perf_counter()
linear_search(small_arr, target)
linear_time = time.perf_counter() - start
# 이진 검색
start = time.perf_counter()
binary_search(small_arr, target)
binary_time = time.perf_counter() - start
print(f"n=10일 때:")
print(f"선형 검색: {linear_time*1000000:.2f} μs")
print(f"이진 검색: {binary_time*1000000:.2f} μs")
# 큰 입력에서 테스트
large_arr = sorted(range(1000000))
target = 999999
start = time.perf_counter()
linear_search(large_arr, target)
linear_time = time.perf_counter() - start
start = time.perf_counter()
binary_search(large_arr, target)
binary_time = time.perf_counter() - start
print(f"\nn=1,000,000일 때:")
print(f"선형 검색: {linear_time*1000:.2f} ms")
print(f"이진 검색: {binary_time*1000:.2f} ms")
print(f"속도 차이: {linear_time/binary_time:.0f}배")
why_big_o_matters()
📊 Big-O 표기법
Big-O는 알고리즘의 최악의 경우 성능을 나타냅니다. 입력 크기 n이 무한대로 갈 때의 성장률을 표현합니다.
주요 복잡도 클래스
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import numpy as np
import matplotlib.pyplot as plt
def visualize_complexities():
"""복잡도 시각화"""
n = np.linspace(1, 100, 100)
complexities = {
'O(1)': np.ones_like(n),
'O(log n)': np.log2(n),
'O(n)': n,
'O(n log n)': n * np.log2(n),
'O(n²)': n ** 2,
'O(2ⁿ)': 2 ** np.minimum(n, 20) # 20 이상은 너무 커서 제한
}
# 복잡도별 성장률 출력
print("입력 크기에 따른 연산 횟수:")
print("-" * 60)
print(f"{'n':<10} {'O(1)':<10} {'O(log n)':<10} {'O(n)':<10} {'O(n log n)':<12} {'O(n²)':<10}")
print("-" * 60)
for size in [1, 10, 100, 1000, 10000]:
o1 = 1
ologn = int(np.log2(size)) if size > 0 else 0
on = size
onlogn = int(size * np.log2(size)) if size > 0 else 0
on2 = size ** 2
print(f"{size:<10} {o1:<10} {ologn:<10} {on:<10} {onlogn:<12} {on2:<10}")
visualize_complexities()
복잡도 순서
graph TB
O1[O<sub>1</sub> - 상수]
Ologn[O<sub>log n</sub> - 로그]
On[O<sub>n</sub> - 선형]
Onlogn[O<sub>n log n</sub> - 선형로그]
On2[O<sub>n²</sub> - 이차]
On3[O<sub>n³</sub> - 삼차]
O2n[O<sub>2ⁿ</sub> - 지수]
Onfact[O<sub>n!</sub> - 팩토리얼]
O1 --> Ologn
Ologn --> On
On --> Onlogn
Onlogn --> On2
On2 --> On3
On3 --> O2n
O2n --> Onfact
style O1 fill:#90EE90
style Ologn fill:#90EE90
style On fill:#90EE90
style Onlogn fill:#FFD700
style On2 fill:#FFD700
style On3 fill:#FFA500
style O2n fill:#FF6347
style Onfact fill:#FF0000
🔍 시간 복잡도 분석
기본 규칙
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class ComplexityRules:
"""Big-O 계산 규칙"""
@staticmethod
def rule1_drop_constants():
"""규칙 1: 상수 무시"""
# O(2n) → O(n)
# O(n/2) → O(n)
# O(1000) → O(1)
def example(n):
# O(3n) = O(n)
for i in range(n):
print(i)
for i in range(n):
print(i)
for i in range(n):
print(i)
@staticmethod
def rule2_drop_lower_terms():
"""규칙 2: 낮은 차수 항 무시"""
# O(n² + n) → O(n²)
# O(n³ + n² + n + 1) → O(n³)
def example(n):
# O(n² + n) = O(n²)
for i in range(n):
for j in range(n):
print(i, j) # n²
for i in range(n):
print(i) # n
@staticmethod
def rule3_different_inputs():
"""규칙 3: 다른 입력은 다른 변수"""
# 두 배열을 처리하면 O(a + b) 또는 O(a * b)
def example(arr1, arr2):
# O(a + b)
for item in arr1:
print(item)
for item in arr2:
print(item)
def example2(arr1, arr2):
# O(a * b)
for item1 in arr1:
for item2 in arr2:
print(item1, item2)
@staticmethod
def rule4_worst_case():
"""규칙 4: 최악의 경우 고려"""
def linear_search(arr, target):
# 최선: O(1) - 첫 번째 원소
# 평균: O(n/2) = O(n)
# 최악: O(n) - 마지막 원소 또는 없음
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
복잡도 분석 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
def analyze_complexity():
"""다양한 코드의 복잡도 분석"""
# O(1) - 상수 시간
def constant_time(arr):
"""배열의 첫 번째 원소 반환"""
if len(arr) > 0:
return arr[0]
return None
# O(log n) - 로그 시간
def logarithmic_time(n):
"""n을 반으로 줄여가며 처리"""
count = 0
while n > 1:
n = n // 2
count += 1
return count
# O(n) - 선형 시간
def linear_time(arr):
"""배열의 합 계산"""
total = 0
for num in arr:
total += num
return total
# O(n log n) - 선형로그 시간
def linearithmic_time(arr):
"""병합 정렬"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = linearithmic_time(arr[:mid])
right = linearithmic_time(arr[mid:])
# 병합 O(n)
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# O(n²) - 이차 시간
def quadratic_time(arr):
"""모든 쌍의 합"""
result = []
for i in range(len(arr)):
for j in range(len(arr)):
result.append(arr[i] + arr[j])
return result
# O(2ⁿ) - 지수 시간
def exponential_time(n):
"""피보나치 (재귀)"""
if n <= 1:
return n
return exponential_time(n-1) + exponential_time(n-2)
# 복잡도 정리
complexities = {
"constant_time": "O(1)",
"logarithmic_time": "O(log n)",
"linear_time": "O(n)",
"linearithmic_time": "O(n log n)",
"quadratic_time": "O(n²)",
"exponential_time": "O(2ⁿ)"
}
print("함수별 시간 복잡도:")
for func, complexity in complexities.items():
print(f" {func:20}: {complexity}")
analyze_complexity()
💾 공간 복잡도 분석
공간 복잡도는 알고리즘이 사용하는 메모리의 양을 나타냅니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class SpaceComplexity:
"""공간 복잡도 예제"""
@staticmethod
def constant_space(arr):
"""O(1) 공간 - 상수 공간"""
# 입력 크기와 관계없이 고정된 변수만 사용
total = 0
max_val = float('-inf')
for num in arr:
total += num
max_val = max(max_val, num)
return total, max_val
@staticmethod
def linear_space(n):
"""O(n) 공간 - 선형 공간"""
# 입력 크기에 비례하는 공간 사용
arr = []
for i in range(n):
arr.append(i * 2)
return arr
@staticmethod
def quadratic_space(n):
"""O(n²) 공간 - 이차 공간"""
# n x n 행렬 생성
matrix = []
for i in range(n):
row = []
for j in range(n):
row.append(i * j)
matrix.append(row)
return matrix
@staticmethod
def recursive_space(n):
"""O(n) 공간 - 재귀 호출 스택"""
# 재귀 깊이가 n이므로 O(n) 공간
if n <= 0:
return 0
return n + SpaceComplexity.recursive_space(n - 1)
@staticmethod
def analyze_space_usage():
"""공간 사용량 분석"""
import sys
# 다양한 자료구조의 메모리 사용량
n = 1000
# 리스트
list_1d = [i for i in range(n)]
list_2d = [[i*j for j in range(n)] for i in range(n)]
# 딕셔너리
dict_small = {i: i*2 for i in range(n)}
# 집합
set_data = set(range(n))
print("메모리 사용량 (bytes):")
print(f"1D 리스트 (n={n}): {sys.getsizeof(list_1d):,}")
print(f"2D 리스트 (n²={n*n}): {sys.getsizeof(list_2d):,}")
print(f"딕셔너리 (n={n}): {sys.getsizeof(dict_small):,}")
print(f"집합 (n={n}): {sys.getsizeof(set_data):,}")
SpaceComplexity.analyze_space_usage()
🎯 복잡도 분석 실전
1. 반복문 분석
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
def loop_complexity_analysis():
"""반복문 복잡도 분석"""
def single_loop(n):
"""단일 반복문 - O(n)"""
count = 0
for i in range(n):
count += 1
return count
def nested_loops(n):
"""중첩 반복문 - O(n²)"""
count = 0
for i in range(n):
for j in range(n):
count += 1
return count
def triple_nested(n):
"""3중 중첩 - O(n³)"""
count = 0
for i in range(n):
for j in range(n):
for k in range(n):
count += 1
return count
def dependent_loops(n):
"""종속적 반복문 - O(n²)"""
count = 0
for i in range(n):
for j in range(i): # j는 i에 종속
count += 1
# 실제 연산 횟수: 1+2+3+...+(n-1) = n(n-1)/2 = O(n²)
return count
def logarithmic_loop(n):
"""로그 반복문 - O(log n)"""
count = 0
i = 1
while i < n:
count += 1
i *= 2 # 매번 2배씩 증가
return count
def nested_different(n, m):
"""다른 크기 중첩 - O(n*m)"""
count = 0
for i in range(n):
for j in range(m):
count += 1
return count
# 테스트
n = 100
print("반복문 실행 횟수:")
print(f"단일 반복문 O(n): {single_loop(n)}")
print(f"중첩 반복문 O(n²): {nested_loops(n)}")
print(f"종속 반복문 O(n²): {dependent_loops(n)}")
print(f"로그 반복문 O(log n): {logarithmic_loop(n)}")
loop_complexity_analysis()
2. 재귀 복잡도 분석
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def recursive_complexity():
"""재귀 함수 복잡도 분석"""
# O(n) - 선형 재귀
def factorial(n):
"""팩토리얼 - T(n) = T(n-1) + O(1) = O(n)"""
if n <= 1:
return 1
return n * factorial(n - 1)
# O(2ⁿ) - 지수 재귀
def fibonacci_naive(n):
"""피보나치 (비효율) - T(n) = T(n-1) + T(n-2) + O(1) = O(2ⁿ)"""
if n <= 1:
return n
return fibonacci_naive(n-1) + fibonacci_naive(n-2)
# O(n) - 최적화된 피보나치
def fibonacci_optimized(n, memo={}):
"""피보나치 (메모이제이션) - O(n)"""
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_optimized(n-1, memo) + fibonacci_optimized(n-2, memo)
return memo[n]
# O(log n) - 이진 탐색
def binary_search_recursive(arr, target, left, right):
"""이진 탐색 - T(n) = T(n/2) + O(1) = O(log n)"""
if left > right:
return -1
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
# 마스터 정리 (Master Theorem)
print("재귀 복잡도 (마스터 정리):")
print("T(n) = aT(n/b) + f(n)")
print("• T(n) = T(n-1) + O(1) → O(n)")
print("• T(n) = 2T(n/2) + O(n) → O(n log n)")
print("• T(n) = 2T(n/2) + O(1) → O(n)")
print("• T(n) = T(n/2) + O(1) → O(log n)")
print("• T(n) = 2T(n-1) + O(1) → O(2ⁿ)")
recursive_complexity()
3. 분할 상환 분석 (Amortized Analysis)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class AmortizedAnalysis:
"""분할 상환 분석"""
@staticmethod
def dynamic_array():
"""동적 배열의 분할 상환 분석"""
class DynamicArray:
def __init__(self):
self.capacity = 1
self.size = 0
self.array = [None] * self.capacity
self.resize_count = 0
self.total_operations = 0
def append(self, value):
if self.size == self.capacity:
# 크기 2배로 확장
self.resize()
self.array[self.size] = value
self.size += 1
self.total_operations += 1
def resize(self):
self.capacity *= 2
new_array = [None] * self.capacity
# 기존 원소 복사 - O(n)
for i in range(self.size):
new_array[i] = self.array[i]
self.total_operations += 1
self.array = new_array
self.resize_count += 1
# 분석
arr = DynamicArray()
n = 1000
for i in range(n):
arr.append(i)
print(f"동적 배열 분할 상환 분석 (n={n}):")
print(f" 총 삽입: {n}")
print(f" 리사이즈 횟수: {arr.resize_count}")
print(f" 총 연산: {arr.total_operations}")
print(f" 평균 연산/삽입: {arr.total_operations/n:.2f}")
print(f" 분할 상환 복잡도: O(1)")
@staticmethod
def stack_with_min():
"""최소값을 O(1)에 반환하는 스택"""
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
if self.stack:
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
return val
def get_min(self):
# O(1) - 분할 상환
return self.min_stack[-1] if self.min_stack else None
print("\n최소값 스택:")
print(" push: O(1)")
print(" pop: O(1)")
print(" get_min: O(1)")
print(" 공간: O(n)")
AmortizedAnalysis.dynamic_array()
AmortizedAnalysis.stack_with_min()
📊 복잡도 비교와 선택
알고리즘 선택 가이드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
def algorithm_selection_guide():
"""상황별 알고리즘 선택 가이드"""
scenarios = {
"작은 데이터 (n < 100)": {
"추천": "간단한 알고리즘 (버블 정렬, 선형 검색)",
"이유": "오버헤드가 적고 구현이 간단",
"복잡도": "O(n²)도 충분히 빠름"
},
"중간 데이터 (100 ≤ n < 10,000)": {
"추천": "효율적인 알고리즘 (퀵 정렬, 이진 검색)",
"이유": "성능과 구현 복잡도의 균형",
"복잡도": "O(n log n) 선호"
},
"큰 데이터 (n ≥ 10,000)": {
"추천": "최적화된 알고리즘 (기수 정렬, 해시 테이블)",
"이유": "성능이 최우선",
"복잡도": "O(n) 또는 O(n log n) 필수"
},
"실시간 시스템": {
"추천": "예측 가능한 알고리즘 (힙 정렬)",
"이유": "최악의 경우도 보장",
"복잡도": "최악 복잡도 중요"
},
"메모리 제한": {
"추천": "제자리 알고리즘 (퀵 정렬, 힙 정렬)",
"이유": "추가 공간 최소화",
"복잡도": "공간 O(1) 또는 O(log n)"
}
}
print("알고리즘 선택 가이드:")
print("=" * 60)
for scenario, info in scenarios.items():
print(f"\n{scenario}:")
for key, value in info.items():
print(f" {key}: {value}")
# 실제 비교 예제
import time
import random
def bubble_sort(arr):
"""O(n²) - 간단하지만 느림"""
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]
def quick_sort(arr):
"""O(n log n) 평균 - 빠름"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
# 성능 비교
sizes = [100, 1000, 5000]
print("\n\n정렬 알고리즘 실제 성능 비교:")
print("-" * 60)
print(f"{'크기':<10} {'버블 정렬 O(n²)':<20} {'퀵 정렬 O(n log n)':<20}")
print("-" * 60)
for size in sizes:
arr1 = [random.randint(1, 1000) for _ in range(size)]
arr2 = arr1.copy()
# 버블 정렬
start = time.perf_counter()
bubble_sort(arr1)
bubble_time = time.perf_counter() - start
# 퀵 정렬
start = time.perf_counter()
quick_sort(arr2)
quick_time = time.perf_counter() - start
print(f"{size:<10} {bubble_time*1000:<20.2f}ms {quick_time*1000:<20.2f}ms")
algorithm_selection_guide()
💡 실전 문제와 복잡도 최적화
문제 1: Two Sum 최적화
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def two_sum_optimization():
"""Two Sum 문제의 복잡도 최적화"""
# O(n²) 해법 - 브루트 포스
def two_sum_naive(nums, target):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
# O(n) 해법 - 해시 테이블
def two_sum_optimized(nums, target):
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
# 비교
nums = [2, 7, 11, 15]
target = 9
print("Two Sum 최적화:")
print(f"입력: {nums}, target = {target}")
print(f"O(n²) 해법: {two_sum_naive(nums, target)}")
print(f"O(n) 해법: {two_sum_optimized(nums, target)}")
print("\n복잡도 비교:")
print(" Naive: 시간 O(n²), 공간 O(1)")
print(" Optimized: 시간 O(n), 공간 O(n)")
two_sum_optimization()
문제 2: 최대 부분 배열 합
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def max_subarray_sum():
"""최대 부분 배열 합 - 복잡도 개선"""
# O(n³) - 브루트 포스
def max_subarray_n3(arr):
n = len(arr)
max_sum = float('-inf')
for i in range(n):
for j in range(i, n):
current_sum = 0
for k in range(i, j + 1):
current_sum += arr[k]
max_sum = max(max_sum, current_sum)
return max_sum
# O(n²) - 개선된 브루트 포스
def max_subarray_n2(arr):
n = len(arr)
max_sum = float('-inf')
for i in range(n):
current_sum = 0
for j in range(i, n):
current_sum += arr[j]
max_sum = max(max_sum, current_sum)
return max_sum
# O(n) - 카데인 알고리즘
def max_subarray_kadane(arr):
max_sum = current_sum = arr[0]
for num in arr[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
# 테스트
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("최대 부분 배열 합:")
print(f"입력: {arr}")
print(f"O(n³) 결과: {max_subarray_n3(arr)}")
print(f"O(n²) 결과: {max_subarray_n2(arr)}")
print(f"O(n) 결과: {max_subarray_kadane(arr)}")
max_subarray_sum()
🎯 핵심 정리
꼭 기억해야 할 5가지
- Big-O는 최악의 경우를 나타냄
- 상수와 낮은 차수 항은 무시
- 입력이 다르면 변수도 다르게 (O(a+b))
- 재귀는 마스터 정리로 분석
- 공간 복잡도도 중요함
복잡도 선택 가이드
- n < 100: 어떤 알고리즘도 OK
- n < 10,000: O(n²)까지 가능
- n < 1,000,000: O(n log n) 필요
- n > 1,000,000: O(n) 또는 O(log n) 필수
💬 면접 질문으로 점검하기
1. Big-O에서 상수와 낮은 차수 항을 왜 버리나요?
Big-O는 입력 크기가 충분히 커질 때 증가 속도를 비교하는 표기법입니다. 3n + 10과 n은 작은 입력에서는 차이가 있지만, 큰 입력에서는 둘 다 선형으로 증가합니다. 그래서 상수와 낮은 차수 항을 제거하고 O(n)으로 표현합니다.
다만 실무 최적화에서는 상수를 완전히 무시하면 안 됩니다. O(n) 알고리즘이라도 네트워크 호출이나 디스크 접근이 반복되면 O(n log n) 메모리 내 연산보다 느릴 수 있습니다.
2. 반복문이 중첩되면 항상 O(n²)인가요?
항상 그렇지는 않습니다. 두 반복문이 모두 같은 입력 n 전체를 순회하면 보통 O(n²)입니다. 하지만 바깥 반복문은 n, 안쪽 반복문은 별도 입력 m을 순회하면 O(nm)입니다. 또 안쪽 반복문이 매번 절반씩 줄어들면 O(n log n)일 수 있습니다.
분석할 때는 “각 반복문이 몇 번 실행되는가”와 “같은 입력을 기준으로 도는가”를 먼저 확인해야 합니다.
3. 공간 복잡도에서 입력 배열도 포함하나요?
일반적인 알고리즘 분석에서는 입력 자체는 제외하고, 알고리즘이 추가로 사용하는 보조 공간을 계산합니다. 예를 들어 입력 배열을 한 번 순회하며 변수 하나만 쓰면 추가 공간은 O(1)입니다. 하지만 입력 크기만큼 해시맵이나 새 배열을 만들면 O(n)입니다.
면접에서는 “입력 공간을 제외한 auxiliary space 기준으로 답하겠다”고 전제하면 오해를 줄일 수 있습니다.
4. 시간 복잡도와 공간 복잡도가 충돌할 때 어떻게 선택하나요?
요구사항이 기준입니다. 응답 시간이 중요하고 메모리가 충분하면 해시맵을 써서 O(n²)을 O(n)으로 줄일 수 있습니다. 반대로 임베디드나 대용량 스트리밍처럼 메모리가 제한되면 느리더라도 공간을 줄이는 알고리즘을 선택할 수 있습니다.
🧪 복잡도 분석 체크리스트
코드를 볼 때 아래 순서로 적어보면 분석 실수가 줄어듭니다.
- 입력 크기를 나타내는 변수를 정한다. 같은 입력이면
n, 다른 입력이면n,m처럼 나눈다. - 기본 연산이 무엇인지 정한다. 비교, 삽입, 조회, 재귀 호출 중 무엇을 세는지 명확히 한다.
- 반복문과 재귀 호출 횟수를 계산한다.
- 해시맵, 정렬, 슬라이싱, 복사처럼 숨은 비용이 있는 연산을 확인한다.
- 시간 복잡도와 공간 복잡도를 따로 적는다.
- 최악, 평균, 최선 중 어떤 경우를 말하는지 표시한다.
📚 추가 학습 자료
추천 자료
- “Introduction to Algorithms” - CLRS
- “Algorithm Design Manual” - Skiena
- Big-O Cheat Sheet (bigocheatsheet.com)
연습 문제
- 주어진 코드의 시간/공간 복잡도 분석
- 복잡도 개선 문제
- 최적 알고리즘 선택 문제
🚀 다음 시간 예고
다음 포스트에서는 정렬 알고리즘을 다룹니다. 버블 정렬부터 퀵 정렬, 기수 정렬까지 모든 정렬 알고리즘을 마스터해보겠습니다!
📌 시리즈 네비게이션
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.