본문 바로가기

알고리즘

Big-O cheat sheet

Big-O(빅오)는 시간 및 공간 복잡도를 나타낼 때 많이 사용한다. 특히 가장 최악의 경우를 고려한 표기법이다.

시간 복잡도를 표현할 때 가장 큰 형태(최고차항)의 값을 남기면 된다. N이 충분히 큰 값이 되어 많은 연산을 한다고 했을 때, 뒤에 더해지는 N의 루프 시간은 그리 중요하지 않기 때문이다.

 

📌 기본 자료구조 시간 복잡도(Big-O)

자료구조 접근(Access) 검색(Search) 삽입(Insertion) 삭제(Deletion)
배열 O(1) O(n) O(n) O(n)
스택 O(n) O(n) O(1) O(1)
O(n) O(n) O(1) O(1)
해시 테이블 N/A O(1) O(1) O(1)
이진 트리 검색 O(nlogn) O(nlogn) O(nlogn) O(nlogn)

 

📌 기본 정렬 알고리즘 시간 복잡도

정렬 알고리즘 최선 평균 최악
퀵 정렬(Quick Sort) O(nlogn) O(nlogn) O(n^2)
병합 정렬(Merge sort) O(nlogn) O(nlogn) O(nlogn)
힙 정렬(Heap sort) O(nlogn) O(nlogn) O(nlogn)
거품 정렬(Bubble sort) O(n) O(n^2) O(n^2)