Big-O Complexity Analysis

알고리즘의 입력 크기(n)에 따른 자원(시간·공간) 소비량을 점근적으로 분석하는 표기법.

계층 구조

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
상수    로그        선형    선형로그       이차      지수      팩토리얼

O(1): 해시 테이블 조회, 배열 인덱스 접근
O(log n): 이진 탐색, 균형 BST 연산
O(n log n): Merge Sort, Heap Sort (최적 비교 정렬)
O(n²): 버블/선택/삽입 정렬, 중첩 반복문

분석 방법

최악(Worst): 표준 기준. 어떤 입력에서도 이 이상 걸리지 않음을 보장.
평균(Average): 입력 분포 가정 필요. QuickSort 평균 O(n log n).
최선(Best): 실용적 의미 적음. 이미 정렬된 삽입 정렬 O(n).

공간 복잡도

재귀 깊이는 스택 프레임으로 공간 소비:

DFS on tree → O(h)  # h = 트리 높이
MergeSort   → O(n)  # 임시 배열
QuickSort   → O(log n) 평균 (in-place 재귀 스택)

연결 노트

• ZK-Hash-Table — O(1) 평균 조회의 구현 기반
• ZK-Consistent-Hashing — 분산 환경에서 O(log n) 노드 조회
• ZK-LLM-Scaling-Laws — 파라미터 스케일과 연산량의 관계도 복잡도 개념