Big-O 표기법 성능 순 정리표

Big-O 표기법 속도 순 정리표

Big-O 표기법을 빠른 순서 ( 성능이 좋은 순서 )로 정리한 표이다.

시간 복잡도 기준으로 정렬되어 있다.

 

 

순위	복잡도	이름 / 성장 형태	예시 알고리즘	설명
1	O(1)	상수 시간 ( Constant )	배열 인덱스 접근 , 스택 Push / Pop	입력 크기와 상관없이 한 번만 연산
2	O(log n)	로그 시간 ( Logarithmic )	이분 탐색 ( Binary Search ) , 균형 BST 탐색	입력이 커져도 단계마다 절반으로 줄어든다
3	O(n)	선형 시간 ( Linear )	단순 순회 ( Loop ) , 선형 탐색	입력 n 개를 한 번씩 처리
4	O(n log n)	준선형 시간 ( Quasi - Linear )	퀵정렬 , 병합정렬 , 힙정렬	n 개 항목 x log n 단계 처리
5	O(n²)	이차 시간 ( Quadratic )	이중 루프 , 버블정렬	모든 쌍을 비교 ( n x n )
6	O(n³)	삼차 시간 ( Cubic )	3중 루프 , 행렬 곱 단순 방식	n x n x n 반복 연산
7	O(nⁿ)	지수 시간 ( Exponential )	재귀 피보나치 , 부분집합 탐색	입력 하나 늘면 2배로 급증
8	O(n!)	팩토리얼 시간 ( Factorial )	순열 생성 , 외판원 문제 ( Brute - Force )	입력 n 개 순서 전부 탐색 ( 매우 비효율 )

 

▼입력 크기 n 이 커질수록 실행 시간은 다음 순서로 급상승한다.

O(1)  <  O(log n)  <  O(n)  <  O(n log n)  <  O(n²)  <  O(2ⁿ)  <  O(n!)

 

 

 

정리

Big-O 는 작을수록 효율적이며, 실제로는 O(1) ~ O(n log n) 사이의 알고리즘이 실용적이다.