시간 복잡도

Big O (빅-오): 상한(upper bound), 최악 사례 복잡도
Big Ω (빅-오메가): 하한(lower bound), 최선 사례 복잡도
Big Θ (빅-쎄타): 상·하한 동시 만족, 평균 사례 복잡도

표기법 (점근적 표기법 사용)

보통 nlogn 이 마지노선이고 $O (n^{2})$ 넘어가면 많은 데이터로 반복적으로계속 써야하는 환경에선 잘 안쓰인다.

분류	표기법	설명	예시 알고리즘
상수 시간	$O (1)$	입력 크기 독립적	배열 원소 접근, 스택 `pop()`
로그 시간	$O (lo g n)$	문제 크기 절반 축소 반복	이진 탐색
선형 시간	$O (n)$	입력 전체 순회	최댓값 탐색, 단순 순회
선형 대수 로그 시간	$O (n lo g n)$	정렬·분할 정복	병합 정렬, 퀵정렬 평균
이차 시간	$O (n^{2})$	중첩 반복문	버블 정렬, 삽입 정렬
지수 시간	$O (2^{n})$	모든 부분집합 탐색	순열 생성, 0-1 배낭 문제 브루트포스