복잡도(Big-O 표기법)

복잡도란?

• 알고리즘이 문제를 해결하는 데 걸리는 시간과 사용하는 메모리 양을 수치적으로 나타낸 것
• 입력 크기 N이 커질수록 성능이 어떻게 변하는지를 분석
• 주로 두 가지를 평가:
  • 시간 복잡도 (Time Complexity)
  • 공간 복잡도 (Space Complexity)

---

시간 복잡도 (Time Complexity)

정의

• 입력 크기 N에 따라 알고리즘이 수행하는 연산 횟수를 수학적으로 표현
• 반복문, 재귀 호출 등을 기준으로 분석
• 일반적으로 최악의 경우(Worst-case) 기준으로 분석

Big-O 표기법이란?

• 가장 영향력이 큰 항만 남기고, 나머지는 생략하는 방식
• 입력이 커질수록 전체 실행 시간에 가장 영향을 주는 항을 남겨 단순화

ex) O(3N² + 2N + 5) → O(N²)

---

주요 시간 복잡도 정리

표기	의미	예시
O(1)	상수 시간	변수 출력, 인덱스 접근 등
O(log N)	로그 시간	이진 탐색
O(N)	선형 시간	리스트 전체 탐색
O(N log N)	선형로그	병합 정렬, 퀵 정렬
O(N²)	이차 시간	이중 반복문
O(2^N)	지수 시간	완전탐색(재귀)
O(N!)	팩토리얼	순열 생성

---

시간 복잡도 예시 코드

# O(1)
def print_first(arr):
    print(arr[0])

# O(N)
def print_all(arr):
    for x in arr:
        print(x)

# O(N²)
def print_pairs(arr):
    for i in arr:
        for j in arr:
            print(i, j)

# 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

---

공간 복잡도 (Space Complexity)

• 알고리즘이 추가로 사용하는 메모리 공간을 분석
• 입력값은 제외하고, 변수, 배열, 재귀 호출 등으로 사용되는 메모리만 고려

예시	공간 복잡도
변수 1개	O(1)
길이 N 배열	O(N)
N x N 이중 배열	O(N²)
재귀 깊이 N	O(N) (스택 사용)

---

입력 크기에 따른 복잡도 한계

입력 크기 N	시간 제한 1초 기준 가능 복잡도
N ≤ 10	O(N!), 완전탐색 가능
N ≤ 100	O(N³) 가능
N ≤ 1,000	O(N²) 가능
N ≤ 100,000	O(N log N) 가능
N ≤ 1,000,000	O(N), O(1)만 가능

---

파이썬 내장 함수 시간 복잡도

함수	시간 복잡도	설명
len(arr)	O(1)	길이 반환
append(x)	O(1)	맨 뒤 추가
insert(i, x)	O(N)	중간 삽입
pop()	O(1)	맨 뒤 제거
pop(i)	O(N)	중간 제거
remove(x)	O(N)	값 찾아 제거
sort()	O(N log N)	TimSort
x in arr (리스트)	O(N)	포함 여부 확인
x in set/dict	O(1)	해시 기반 탐색

---

실전 팁 요약

• 중첩 반복문 줄이기
• 정렬 후 이진 탐색 적용
• set, dict 활용으로 탐색 속도 개선
• 입력이 많을 경우 sys.stdin.readline()으로 입력 처리 최적화

---

핵심 요약

항목	설명
시간 복잡도	연산 횟수 (속도 분석)
공간 복잡도	메모리 사용량
Big-O 표기법	가장 영향력 있는 항만 남김
파이썬 주요 함수 복잡도	알고 있어야 성능 분석 가능
입력 범위에 따른 제한	문제 조건 보고 적절한 알고리즘 판단 필요