시간 복잡도 (Time Complexity)

개념

• 프로그램이 실행되는 데 걸리는 시간이 입력 크기(데이터 양)에 따라 어떻게 늘어나는지를 나타냄.

• 보통 Big O 표기법(O(1), O(N), O(N²) 등)으로 쓴다.

특징

• 효율적인 알고리즘을 선택할 때 중요하다.

• 입력이 많아질수록 시간 복잡도가 낮은(빅오가 작은) 알고리즘이 더 빨리 동작한다.

• 보통 최악의 경우(최대 시간) 기준으로 복잡도를 계산한다.

• 시간 복잡도가 낮을수록 대용량 데이터를 더 빠르게 처리할 수 있다

  예시

  for i in range(N):
    print(i)
  # O(N) - N번 반복
  

  for i in range(N):
    for j in range(N):
        print(i, j)
  # O(N²) - N*N번 반복 (이중 for문)
  

  
  
  

공간 복잡도 (Space Complexity)

개념

• 프로그램이 사용하는 메모리 공간이 입력 크기에 따라 얼마나 증가하는지 나타냄.

• 마찬가지로 Big O 표기법으로 쓴다.

특징

• 메모리가 제한된 환경에서는 공간 복잡도도 중요하다.

• 메모리 초과 되어 비정상 종료 당하지 않으려면 주의해야한다.

• 반복문은 일반적으로 공간 복잡도가 낮고, 재귀 함수는 호출 스택¹ 때문에 공간 복잡도가 높아질 수 있다.

  • 반복문 팩토리얼: O(1)
  • 재귀 팩토리얼: O(N) (스택에 함수가 N번 쌓이기 때문)

예시

a = [0] * N  # N개의 리스트 생성
# O(N)

def f(n):
    if n == 0:
        return
    f(n-1)
# O(N) - 함수 호출 스택이 N개 쌓임

Big O 표기법

개념

• 입력 크기가 무한히 커질 때 성능이 어떻게 변하는지 나타내는 수식.

• 알고리즘의 효율을 한눈에 비교할 수 있게 해줌.

  특징

• 상수와 작은 항은 무시한다: 예를 들어, O(2N + 10)은 O(N)으로 표기함.

• 성장 속도(Scale) 를 비교한다.

• 보통 최악의 경우 (가장 큰 Big O)를 표기하지만, 필요에 따라 평균/최선의 경우도 분석할 수 있다.

예시

• O(1): 입력 크기에 상관없이 한 번만 동작 (ex: 변수값 출력)

• O(N): 입력 크기만큼 동작 (ex: 리스트 한 번 순회)

• O(N²): 입력 크기 제곱만큼 동작 (ex: 이중 for문)

• O(logN): 이진탐색 (입력이 커져도 비교적 느리게 늘어남)

• O(2^N): 경우의 수가 2의 N승 (ex: 부분집합, 순열 등)

표로 비교

시간 복잡도와 공간 복잡도 비교표