공간 복잡도는 입력 증가에 따른 최대 저장 공간을 분석한다. 입력·출력·보조 공간, 복사와 참조, 재귀·제너레이터·캐시를 구분하고 LCS·배낭의 공간 압축과 실제 메모리 측정을 검증 예제로 설명한다. 공간 복잡도(space complexity)는 입력 크기가 늘 때 알고리즘이 사용하는 저장 공간이 어떻게 증가하는지 분석하는 개념이다. 특정 컴퓨터에서 몇 MB를 썼는지 측정하는 것과 관련은 있지만 같은 수치는 아니다. 입력·출력
시간 복잡도는 입력 크기에 따른 알고리즘 작업량의 증가를 분석한다. 이 문서는 O·Ω·Θ, 최선·최악·기댓값·분할 상환 분석을 구분하고, 반복문·재귀·복사·해시·전처리 비용을 실제 연산 횟수 예제로 계산한다. 시간 복잡도는 입력 크기에 따라 알고리즘의 작업량이 어떻게 증가하는지 표현하는 개념이다. “이 함수는 0.2초 걸린다”는 특정 실행의 측정과 다르다. 같은 알고리즘도 컴퓨터, 언어, 입력 내용에 따라 실제 시간이 달라지므