[Python-알고리즘] 복잡도

복잡도(Big O), 시간복잡도, 공간복잡도 정리 및 예시

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

빅오 표기법은 알고리즘의 효율성을 평가하는 방법으로, 입력 크기(n)에 따른 실행 시간 또는 공간 사용량의 상한을 나타냅니다.
즉, 입력 크기가 커질 때 알고리즘이 얼마나 느려지는지 혹은 메모리를 얼마나 더 사용하는지를 간략하게 표현합니다.

중요 개념:
- O(1): 입력 크기와 관계없이 일정한 시간(또는 공간) 사용
- O(n): 입력 크기에 비례하여 선형 증가
- O(log n): 입력 크기에 로그 비례 (예: 이진 탐색)
- O(n^2): 입력 크기의 제곱에 비례 (예: 이중 반복문)
- O(2^n): 지수적으로 증가 (예: 모든 부분집합 탐색)

2. 시간복잡도 (Time Complexity)

시간복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 크기 n의 함수로 나타냅니다.
보통 최악의 경우(최대 실행 시간)를 기준으로 평가합니다.

2-1. 자주 쓰이는 시간복잡도 유형과 예시

• O(1): 배열에서 특정 인덱스 값 접근 (예: arr[5])
• O(n): 배열을 한 번 순회하며 합 계산하기
• O(log n): 이진 탐색 (정렬된 배열에서 값 찾기)
• O(n log n): 효율적인 정렬 알고리즘(예: 퀵정렬, 병합정렬)
• O(n^2): 이중 반복문으로 모든 쌍 비교하기 (예: 버블정렬)

2-2. 예시 코드와 시간복잡도 설명

O(1) 예시: 배열 인덱스 접근

def get_element(arr, index):
    return arr[index]  # 한 번만 접근하므로 O(1)

O(n) 예시: 리스트 합 계산

def sum_list(arr):
    total = 0
    for num in arr:  # n번 반복
        total += num
    return total  # 전체 실행 시간은 입력 크기 n에 비례 -> O(n)

O(n^2) 예시: 중첩 반복문으로 모든 쌍 출력

def print_pairs(arr):
    n = len(arr)
    for i in range(n):        # n번 반복
        for j in range(n):    # n번 반복
            print(arr[i], arr[j])  # 총 n * n = n²번 수행 -> O(n²)

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)

3. 공간복잡도 (Space Complexity)

공간복잡도는 알고리즘이 문제를 해결하는 데 필요한 메모리 공간을 입력 크기 n의 함수로 나타냅니다.
입력 크기가 증가할 때 추가로 필요한 메모리 양을 평가합니다.

3-1. 예시와 공간복잡도 분석

O(1) 공간복잡도: 변수 하나만 사용하는 경우

def find_max(arr):
    max_val = arr[0]  # 상수 공간 사용
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val
# 입력 크기에 관계없이 max_val 변수 하나만 사용 -> O(1)

O(n) 공간복잡도: 입력 크기만큼 추가 공간 필요

def copy_list(arr):
    new_arr = []
    for num in arr:
        new_arr.append(num)  # 입력 크기만큼 새 리스트에 저장
    return new_arr
# 입력 크기 n에 비례하는 새로운 리스트 생성 -> O(n)

4. 빅오 시간복잡도 표 (입력 크기 n 증가에 따른 실행 시간 예시)

입력 크기 (n)	O(1)	O(log n)	O(n)	O(n log n)	O(n²)	O(2^n)
10	1	4	10	40	100	1024
100	1	7	100	700	10,000	1.27e30
1,000	1	10	1,000	10,000	1,000,000	~1.07e301

5. 참고: 최선, 평균, 최악의 시간복잡도

알고리즘은 상황에 따라 실행 시간이 다릅니다.
- 최선(best case): 가장 빠른 실행 시간
- 평균(average case): 평균적인 실행 시간
- 최악(worst case): 가장 느린 실행 시간 (빅오는 보통 최악 기준)

예시: 퀵 정렬 시간복잡도

• 최선, 평균: O(n log n)
• 최악 (이미 정렬된 배열 등): O(n^2)

6. 요약

• 빅오는 알고리즘의 효율성을 평가하는 수학적 표기법입니다.
• 시간복잡도는 실행 시간 증가율, 공간복잡도는 메모리 사용 증가율을 의미합니다.
• 효율적인 알고리즘 설계 시 시간과 공간 복잡도를 모두 고려해야 합니다.
• 빅오는 최악의 상황을 표현하며, 최선과 평균도 경우에 따라 고려해야 합니다.