시간복잡도와 공간 복잡도

시간 복잡도(Time Complexity)

알고리즘의 실행 시간이 입력 크기에 대해 어떻게 증가하는지를 나타내는 척도

 

공간 복잡도(Space Complexity)

알고리즘이 실행되는 동안 사용하는 메모리 공간의 양

 

빅오 표기법(Big O Notation)

알고리즘의 성능을 수학적으로 표현하는 방법으로, 최악의 경우를 기준으로 합니다.

# O(1) - 상수 시간
def constant_time(arr):
    return arr[0] if arr else None

# O(n) - 선형 시간
def linear_time(arr):
    total = 0
    for num in arr:
        total += num
    return total

# O(n²) - 제곱 시간
def quadratic_time(arr):
    result = []
    for i in arr:
        for j in arr:
            result.append(i + j)
    return result

# 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

# 시간 복잡도 비교 예제
import time

def measure_time(func, *args):
    start = time.time()
    result = func(*args)
    end = time.time()
    print(f"{func.__name__}: {end - start:.6f}초")
    return result

# 예제
test_array = list(range(1000))
measure_time(constant_time, test_array)
measure_time(linear_time, test_array)