2025-07-31 00:30

Status:

Tags: 자료구조 알고리즘

시간 복잡도

• 입력이 무한에 가깝게 늘어날때 어느정도 수준으로 늘어날까?

• 무한도 급이 있다.

• N 이 계속해서 커지면 어떤 추세로 커질까

• 최악 사례 복잡도(worst-case): 입력 중 가장 시간이 오래 걸리는 경우의 연산 수

• 평균 사례 복잡도(average-case): 모든 가능한 입력에 대한 평균 연산 수

• 상수 계수 및 낮은 차수 항 무시: $O(f(n))$ 표기법에서는 상수 계수와 낮은 차수 항은 생략한다[^1].

표기법

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

시간복잡도 비교

보통 nlogn 이 마지노선이고 $O(n^2)$ 넘어가면 잘 안쓰인다.

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

References

시간 복잡도 핸드북