빅오 표기법

빅오(O) 표기법

빅오(Big-O) 표기법: 알고리즘의 성능을 입력 크기에 따라 객관적으로 표현하는 방식. 최악의 경우(Worst Case)를 기준으로 표기한다.

왜 사용하는가?

• 알고리즘의 성능을 입력 크기에 따라 객관적으로 표현하기 위해
• 최선/최악/평균의 경우를 분석하여 자료구조 및 알고리즘 선택의 기준으로 활용

특이점

• 상수 계수와 낮은 차항은 무시한다 (n이 매우 클 때 지배적인 항만 고려)
• 최악의 경우(Worst Case)를 기준으로 표기하는 것이 일반적

시간 복잡도 종류

표기	이름	설명	예시
O(1)	상수 시간	입력 크기와 무관하게 일정	배열 인덱스 접근, 해시 조회
O(log n)	로그 시간	입력이 2배 늘어날 때 연산 1번 추가	이진 탐색, TreeMap 조회
O(n)	선형 시간	입력에 비례하여 증가	배열 순회, 선형 탐색
O(n log n)	선형 로그 시간	정렬 알고리즘의 이상적 복잡도	Arrays.sort(), mergeSort
O(n²)	제곱 시간	이중 반복문	버블 정렬, 선택 정렬

성능 비교

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
빠름 ←——————————————————————————————→ 느림

상황별 가정

경우	복잡도	설명
최적 (Best Case)	O(1)	첫 번째 시도에 찾는 경우
평균 (Average Case)	O(n/2) → O(n)	중간 위치에서 찾는 경우
최악 (Worst Case)	O(n)	마지막 위치 또는 존재하지 않는 경우

자료구조별 시간 복잡도

자료구조	접근	검색	삽입	삭제
배열	O(1)	O(n)	O(n)	O(n)
ArrayList	O(1)	O(n)	O(n)	O(n)
LinkedList	O(n)	O(n)	O(1)	O(1)
HashSet/HashMap	-	O(1)	O(1)	O(1)
TreeSet/TreeMap	-	O(log n)	O(log n)	O(log n)
Stack/Queue	O(n)	O(n)	O(1)	O(1)

어떨 때 많이 쓰는가?

• 자료구조 선택 시 성능 요구 사항 분석
• 알고리즘 개선 전/후 성능 비교
• 코드 리뷰에서 병목 지점 파악
• 기술 면접에서 코드의 효율성 설명