01_complexity.py - Examples

  1"""
  2시간 복잡도 비교 실험
  3Time Complexity Comparison
  4
  5다양한 시간 복잡도를 가진 알고리즘들의 실행 시간을 비교합니다.
  6"""
  7
  8import time
  9import random
 10
 11
 12def measure_time(func, *args):
 13    """함수 실행 시간 측정"""
 14    start = time.perf_counter()
 15    result = func(*args)
 16    end = time.perf_counter()
 17    return end - start, result
 18
 19
 20# =============================================================================
 21# O(1) - 상수 시간
 22# =============================================================================
 23def constant_time(arr):
 24    """배열의 첫 번째 요소 반환 - O(1)"""
 25    if arr:
 26        return arr[0]
 27    return None
 28
 29
 30# =============================================================================
 31# O(log n) - 로그 시간
 32# =============================================================================
 33def binary_search(arr, target):
 34    """이분 탐색 - O(log n)"""
 35    left, right = 0, len(arr) - 1
 36    while left <= right:
 37        mid = (left + right) // 2
 38        if arr[mid] == target:
 39            return mid
 40        elif arr[mid] < target:
 41            left = mid + 1
 42        else:
 43            right = mid - 1
 44    return -1
 45
 46
 47# =============================================================================
 48# O(n) - 선형 시간
 49# =============================================================================
 50def linear_search(arr, target):
 51    """선형 탐색 - O(n)"""
 52    for i, val in enumerate(arr):
 53        if val == target:
 54            return i
 55    return -1
 56
 57
 58def find_max(arr):
 59    """최댓값 찾기 - O(n)"""
 60    if not arr:
 61        return None
 62    max_val = arr[0]
 63    for val in arr:
 64        if val > max_val:
 65            max_val = val
 66    return max_val
 67
 68
 69# =============================================================================
 70# O(n log n) - 선형 로그 시간
 71# =============================================================================
 72def merge_sort(arr):
 73    """병합 정렬 - O(n log n)"""
 74    if len(arr) <= 1:
 75        return arr
 76
 77    mid = len(arr) // 2
 78    left = merge_sort(arr[:mid])
 79    right = merge_sort(arr[mid:])
 80
 81    result = []
 82    i = j = 0
 83    while i < len(left) and j < len(right):
 84        if left[i] <= right[j]:
 85            result.append(left[i])
 86            i += 1
 87        else:
 88            result.append(right[j])
 89            j += 1
 90    result.extend(left[i:])
 91    result.extend(right[j:])
 92    return result
 93
 94
 95# =============================================================================
 96# O(n²) - 제곱 시간
 97# =============================================================================
 98def bubble_sort(arr):
 99    """버블 정렬 - O(n²)"""
100    arr = arr.copy()
101    n = len(arr)
102    for i in range(n):
103        for j in range(0, n - i - 1):
104            if arr[j] > arr[j + 1]:
105                arr[j], arr[j + 1] = arr[j + 1], arr[j]
106    return arr
107
108
109def has_duplicate_naive(arr):
110    """중복 검사 (naive) - O(n²)"""
111    n = len(arr)
112    for i in range(n):
113        for j in range(i + 1, n):
114            if arr[i] == arr[j]:
115                return True
116    return False
117
118
119# =============================================================================
120# O(2^n) - 지수 시간
121# =============================================================================
122def fibonacci_recursive(n):
123    """피보나치 (재귀) - O(2^n)"""
124    if n <= 1:
125        return n
126    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
127
128
129def fibonacci_dp(n):
130    """피보나치 (DP) - O(n)"""
131    if n <= 1:
132        return n
133    dp = [0] * (n + 1)
134    dp[1] = 1
135    for i in range(2, n + 1):
136        dp[i] = dp[i - 1] + dp[i - 2]
137    return dp[n]
138
139
140# =============================================================================
141# 실험 및 결과 출력
142# =============================================================================
143def run_experiments():
144    """시간 복잡도 실험 실행"""
145    print("=" * 60)
146    print("시간 복잡도 비교 실험")
147    print("=" * 60)
148
149    # 데이터 준비
150    sizes = [100, 1000, 10000]
151
152    for size in sizes:
153        print(f"\n[ 배열 크기: {size} ]")
154        print("-" * 40)
155
156        arr = list(range(size))
157        random_arr = random.sample(range(size * 10), size)
158        target = arr[size // 2]  # 중간 값
159
160        # O(1) 테스트
161        t, _ = measure_time(constant_time, arr)
162        print(f"O(1)     상수 시간:      {t * 1000:.6f} ms")
163
164        # O(log n) 테스트
165        t, _ = measure_time(binary_search, arr, target)
166        print(f"O(log n) 이분 탐색:      {t * 1000:.6f} ms")
167
168        # O(n) 테스트
169        t, _ = measure_time(linear_search, arr, target)
170        print(f"O(n)     선형 탐색:      {t * 1000:.6f} ms")
171
172        t, _ = measure_time(find_max, random_arr)
173        print(f"O(n)     최댓값 찾기:    {t * 1000:.6f} ms")
174
175        # O(n log n) 테스트
176        if size <= 10000:
177            t, _ = measure_time(merge_sort, random_arr)
178            print(f"O(n log n) 병합 정렬:  {t * 1000:.6f} ms")
179
180        # O(n²) 테스트 (작은 크기만)
181        if size <= 1000:
182            t, _ = measure_time(bubble_sort, random_arr)
183            print(f"O(n²)    버블 정렬:      {t * 1000:.6f} ms")
184
185    # O(2^n) vs O(n) 피보나치 비교
186    print("\n[ 피보나치 비교: O(2^n) vs O(n) ]")
187    print("-" * 40)
188
189    for n in [10, 20, 30]:
190        t_recursive, _ = measure_time(fibonacci_recursive, n)
191        t_dp, _ = measure_time(fibonacci_dp, n)
192        print(f"n={n}: 재귀 O(2^n) = {t_recursive * 1000:.4f} ms, "
193              f"DP O(n) = {t_dp * 1000:.6f} ms")
194
195    print("\n" + "=" * 60)
196    print("실험 완료!")
197    print("=" * 60)
198
199
200if __name__ == "__main__":
201    run_experiments()