Complexity Analysis & Big-O

1. Overview

복잡도 분석 및 Big-O(Complexity Analysis & Big-O, CAB)는 알고리즘의 '품질'을 측정하는 글로벌 표준 도량형이자, 소프트웨어가 거대한 데이터 앞에서 무너지지 않을 것임을 증명하는 수리적 안전장치입니다.

성능은 "초"라는 물리적 시간으로만 측정하지 않습니다. 컴퓨터 성능은 제각각이기 때문입니다. 학습자는 입력 데이터의 크기($n$)가 무한히 커질 때 연산 횟수가 증가하는 추세인 **점근적 분석(Asymptotic Analysis)**을 배웁니다. 특히 성능의 최악 상한선을 긋는 Big-O를 중심으로, 평균적인 Big-Theta($\Theta$), 최소 하한선인 **Big-Omega($\Omega$)**의 수리적 의미를 익힙니다. 이를 통해 단순히 "작동하는 코드"를 넘어 "수조 개의 데이터를 견디는 강인한 코드"를 감별하는 통찰력을 확보합니다.

2. Scope & Boundaries

In-Scope

• Asymptotic Notations: Big-O, $\Omega$, $\Theta$의 정의와 수리적 판정 물리
• Time Complexity Analysis: 루프, 조건문, 재귀 호출의 연산 횟수 정량화
• Space Complexity Mechanics: 변수, 데이터 구조, 호출 스택이 점유하는 물리 램(RAM) 용량 산출
• Comparison Cases: $O(1), O(\log n), O(n), O(n \log n), O(n^2), O(2^n)$의 성능 격차 분석

Out-of-Scope

• 알고리즘 자체의 구체적인 구현 코드 (해당 알고리즘 노드로 위임)
• 계산 이론(Computability) 및 P-NP 문제 상세 (04-03-04 노드에서 분담)

Boundaries

• CAB vs. Benchmarking: 벤치마킹이 '특정 기계에서의 실측값'을 잰다면, CAB은 '기계와 상관없는 알고리즘 고유의 수리적 체급'을 다룸으로써 실무와 이론의 경계를 가릅니다.

3. Counterexample

• 단순히 "빠르면 좋은 것"이라 말하는 것은 CAB 학습이 아닙니다. $1,000,000n$과 $n^2$ 알고리즘 중, 데이터 개수($n$)가 적을 때는 왜 성능이 역전되는지 물리적 임계점 관점에서 증명할 수 있어야 하며, 시간 복잡도를 줄이기 위해 메모리를 더 쓰는 공간 복잡도와의 '트레이드-오프(Trade-off)' 관계를 수리적으로 설명하지 못한다면 CAB의 실전적 의미를 이해하지 못한 것입니다.

4. Prerequisites

• Arrays, Strings & Memory Layout (Basic): 데이터 저장 단위 기초가 필수입니다. (04-01-01 ASL)
• Computer Organization Physics (Recommended): CPU 연산 주기 이해가 권장됩니다. (02-01-XX)

5. Learning Map

1. The Scale Problem: 데이터가 10개일 때와 1억 개일 때 알고리즘이 느끼는 물리 압박의 차이를 인식합니다.
2. Asymptotic Lens: 자잘한 상수를 버리고 거대한 추세(Dominant Term)만 포착하는 법을 배웁니다.
3. The Big-O Wall: 내 알고리즘이 절대로 넘지 않을 최악의 시간 장벽을 수리적으로 설계합니다.
4. Efficiency Trade-offs: 시간(Time)을 살리기 위해 공간(Space)을 제물로 바치는 자원 배분을 완성합니다.

6. Learning Topics

Basic

Core: 점근적 표기법의 정의 (Asymptotic Notations)

• Why to Learn: 하드웨어 성능과 상관없이 알고리즘 자체의 물리적 효율성을 비교할 수 있는 공용어를 쓰기 위함입니다.
• What to Learn:
  • Growth Rate: $n$의 증가에 따른 연산 기울기 물리
  • Big-O Definition: $f(n) \le C \cdot g(n)$을 만족하는 물리적 경계
  • Worst, Average, Best Cases: 운이 좋을 때와 나쁠 때의 알고리즘 운명 분석
• How to Learn:
  • $n, \log n, n^2$ 그래프를 직접 그려보고, $n$이 커질수록 서로의 물리적 거리가 얼마나 기하급수적으로 멀어지는지 확인 실습
  • 알고리즘 코드에서 '가장 많이 실행되는 문장' 한 줄을 찾아내어 전체 복잡도의 대표 지표로 선정하는 훈련
• Implement: 입력값에 따른 연산 횟수를 카운팅하여 결과를 출력하는 간단한 성능 분석기

Recommended

Core: 시간 복잡도의 정량적 분석 (Analyzing Operations)

• Why to Learn: 코드를 한 줄 쓸 때마다 그게 시스템 전체에 지불할 '물리적 비용'이 얼마인지 계산하기 위해서입니다.
• What to Learn:
  • Primitive Operations: 대입, 비교, 산술 연산의 고정 원자 비용
  • Nested Loops: 이중 루프가 왜 $n^2$으로 수렴하는지에 대한 기하학적 증명
  • Divide and Conquer Complexity: 문제를 쪼갤 때 발생하는 $\log n$의 물리 기원
• How to Learn:
  • 버블 정렬과 퀵 정렬의 연산 횟수를 추적하며, $O(n^2)$과 $O(n \log n)$이 실전 데이터에서 어떤 속도 격차를 내는지 관찰 실습
  • 조건문(If-else)이 있을 때 최악의 경로를 따라가며 시간 비용 합산 훈련
• Implement: 정해진 알고리즘의 복잡도를 추론하고 그 근거를 단계별로 기술하는 분석 보고서

Practical

Core: 공간 복잡도와 메모리 점유 (Space Complexity)

• Why to Learn: 시간이 아무리 빨라도 메모리가 부족해 시스템이 터지면(Crash) 무용지물이기 때문입니다.
• What to Learn:
  • Auxiliary Space: 순수하게 알고리즘 수행을 위해 추가로 필요한 물리 메모리
  • Recursion Depth Stack: 재귀 호출이 깊어질 때 시스템 스택에 쌓이는 물리 데이터양
  • Space-Time Trade-off: 메모리에 미리 계산해 두어(Memoization) 시간을 버는 지능적 설계
• How to Learn:
  • 피보나치 수열을 단순 재귀와 동적 계획법으로 짰을 때, 각각의 물리적 램 점유율과 호출 스택 높이 비교 실습
  • 데이터 구조(배열 vs 리스트) 선택에 따른 메모리 오버헤드 수리적 산출
• Implement: 데이터 처리를 수행하며 런타임에 메모리 사용 피크(Peak)를 측정하는 프로파일링 코드

Advanced

Core: 분할 상환 및 분산 분석 (Amortized Analytics)

• Why to Learn: 가끔 한 번 발생하는 '폭탄(무거운 연산)'이 전체 평균 성능을 망치지 않음을 수리적으로 방어하기 위함입니다.
• What to Learn:
  • Aggregate Analysis: 전체 연산 시퀀스의 총합 비용을 연산 개수로 나누는 물리 평탄화
  • Accounting Method: 돈(비용)을 미리 저축해 두었다가 무거운 일이 터질 때 쓰는 자금 모델링
  • Complexity Classes (NP-Complete): 현대의 어떤 컴퓨터로도 물리적 시간 내에 풀 수 없는 영역의 인지
• How to Learn:
  • 동적 배열(Dynamic Array)의 확장 과정에서 발생하는 복사 비용이 왜 전체로 나누면 $O(1)$이 되는지 수리적으로 증명 실습
  • 외판원 문제(TSP)를 통해 데이터 100개만 넘어도 우주의 수명보다 긴 물리 시간이 필요함을 체감
• Implement: 비싼 비용이 가끔 드는 작업을 수천 번 수행하며 전체 지출 비용의 평균을 수렴시키는 시뮬레이션

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Software Engineering Foundations / Theoretical Foundations — Algorithm analysis.
• [P1] CS2023 - AL/Algorithms and Complexity (Basic Analysis) — Core requirements.

Secondary

• [Introduction to Algorithms (CLRS)] Cormen — The definitive complexity reference.
• [The Algorithm Design Manual] Steven Skiena — Practical Big-O guidance.

Industry

• [Google: Tech Dev Guide (Complexity Analysis)] — Industry application rules.
• [Big O Cheat Sheet] — Quick reference for standard data structures.

9. Final Checklist

Primary

• 입력값 $n$이 2배가 될 때, 연산 시간이 4배로 늘어나는 알고리즘의 'Big-O' 지수를 수리적으로 도출할 수 있는 가? (P1)
• 알고리즘 성능 지표에서 왜 $O(100n)$에서 상수 '100'을 물리적으로 무시하고 $O(n)$으로 표기하는지 그 수렴 원리를 설명 가능한가? (P1)

Secondary

• 최악의 경우(Worst case) 분석이 왜 실무 시스템 설계에서 **최선의 경우(Best case)**보다 물리적인 신뢰 보증 지표로 가치 있는지 소통 가능한가?
• 재귀 알고리즘을 사용했을 때 발생하는 '공간 복잡도'가 단순 반복문보다 왜 물리적으로 큰 리스크를 갖는지 도출할 수 있는 가?

Industry

• 수백만 이용자의 검색 엔진 설계 시, $O(n)$ 검색 대신 $O(\log n)$ 검색(이진 탐색 등)을 선택했을 때 얻는 물리적 서버 비용 절감 효과를 제안할 수 있는 가? (SFIA)
• 클라우드 시스템에서 'Time-Space Trade-off'를 활용하여 API 응답 속도를 높이기 위한 '캐싱' 전략의 수리적 한계 비용을 기술할 수 있는 가?