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) |
'알고리즘' 카테고리의 다른 글
[백준] 4375번: 1 (java, python, 나머지 연산) (0) | 2022.09.25 |
---|---|
[백준] 2609번: 최대공약수와 최소공배수(java, python) (2) | 2022.09.20 |
[프로그래머스] 문자열 압축(python) (0) | 2022.08.20 |
[프로그래머스] 오픈채팅방(python) (0) | 2022.08.20 |
[프로그래머스] 없는 숫자 더하기(python) (0) | 2022.08.20 |