# 계산 복잡도 (Computational Complexity)

계산 복잡도란 특정 알고리즘이 실행될 때 소요되는 시간과 공간의 양을 입력 크기에 따라 나타낸 것입니다. 이는 알고리즘의 효율성을 객관적으로 측정하고 비교하기 위한 척도로 사용됩니다.

## 시간 복잡도 (Time Complexity)

시간 복잡도는 입력 값의 크기($n$)가 증가함에 따라 알고리즘의 실행 시간이 어떻게 변하는지를 나타냅니다.

### 빅오 표기법 (Big-O Notation)
빅오 표기법은 알고리즘의 효율성을 나타내는 표준적인 방법으로, 입력 크기가 무한히 커질 때의 상한선(Upper Bound)을 표현합니다. 세부적인 상수항이나 낮은 차수의 항을 무시하고 가장 영향력이 큰 항만을 남겨 표현함으로써, 하드웨어 성능과 관계없이 알고리즘 자체의 논리적 효율성을 분석할 수 있게 해줍니다.

### 주요 복잡도 단계

| 표기법 | 명칭 | 설명 | 예시 알고리즘 |
| :--- | :--- | :--- | :--- |
| $O(1)$ | 상수 시간 (Constant) | 입력 크기와 상관없이 항상 일정한 시간이 걸림 | 배열의 인덱스 접근 |
| $O(\log n)$ | 로그 시간 (Logarithmic) | 입력 크기가 커질수록 실행 시간이 로그 함수 형태로 증가 | 이진 탐색 (Binary Search) |
| $O(n)$ | 선형 시간 (Linear) | 입력 크기에 비례하여 실행 시간이 증가 | 선형 탐색 (Linear Search) |
| $O(n \log n)$ | 선형 로그 시간 (Linearithmic) | 입력 크기에 $\log n$을 곱한 만큼 증가 | 퀵 정렬, 병합 정렬 |
| $O(n^2)$ | 이차 시간 (Quadratic) | 입력 크기의 제곱에 비례하여 실행 시간이 증가 | 버블 정렬, 삽입 정렬 |
| $O(2^n)$ | 지수 시간 (Exponential) | 입력 크기가 증가함에 따라 실행 시간이 기하급수적으로 증가 | 피보나치 수열 (재귀 구현) |

## 공간 복잡도 (Space Complexity)

공간 복잡도는 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 입력 크기에 따라 나타낸 것입니다. 여기에는 알고리즘이 사용하는 고정 공간(코드, 단순 변수 등)과 입력 크기에 따라 변하는 가변 공간(동적 할당, 재귀 호출 스택 등)이 포함됩니다.

**예시:**
- 입력 배열의 크기만큼 새로운 배열을 생성하는 알고리즘은 $O(n)$의 공간 복잡도를 가집니다.
- 추가적인 메모리 할당 없이 변수 몇 개만 사용하여 처리하는 알고리즘은 $O(1)$의 공간 복잡도를 가집니다.

## 최악/평균/최선의 경우

알고리즘의 성능은 입력 데이터의 상태에 따라 달라질 수 있으므로 세 가지 관점에서 분석합니다.

1. **최악의 경우 (Worst-case)**: 입력 데이터가 알고리즘이 가장 오래 걸리도록 배치된 경우입니다. 대부분의 분석에서 보장할 수 있는 최대 실행 시간을 의미하므로 가장 중요하게 다뤄집니다.
2. **평균의 경우 (Average-case)**: 모든 가능한 입력에 대해 실행 시간을 평균 낸 값입니다. 실제 환경에서의 성능을 예측하는 데 유용합니다.
3. **최선의 경우 (Best-case)**: 입력 데이터가 알고리즘이 가장 빠르게 처리될 수 있도록 배치된 경우입니다. 실질적인 성능 지표로는 잘 사용되지 않습니다.

## 예시 코드

### 선형 탐색 (Linear Search) $\rightarrow O(n)$
```python
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # 찾았을 때 즉시 반환
    return -1  # 찾지 못했을 때
```

### 이진 탐색 (Binary Search) $\rightarrow O(\log n)$
```python
def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1
```