알고리즘
Big O 표기법
미역제자
2024. 7. 1. 16:38
Big O 표기법은 최악의 경우 알고리즘 수행 시간을 나타낸다.
아래 표는 효율적인 순서대로 작성했다.
| Big O | 형태 | 설명 | 추천 알고리즘 |
| O(1) | 상수 형태 | 해당 알고리즘이 일정한 상수 시간에 종료됨. | 해시 테이블 |
| O(log n) | 로그 형태 | 입력값 n이 증가하는 속도보다 수행시간이 천천히 증가하는 알고리즘. | 이진 탐색, 유클리드 호제법 |
| O(n) | 선형 | 입력값 n 만큼의 수행시간을 요구함. | 순차 탐색 |
| O(n log n) | 선형로그 형태 | 선형 로그 형태로 수행시간이 필요함. | 병합 정렬, 퀵 정렬, 힙 정렬 |
| O(n ^ 2) | 다차 형태 | n에 대한 다차 형태로 수행시간이 증가함. for문이 중첩되어있는 만큼 지수가 증가함. |
버블 정렬, 삽입 정렬, 선택 정렬 행렬 곱셉 ( O(n ^ 3) ) |
| O(2 ^ n) | 지수 형태 | n이 지수인 형태로 수행시간이 증가함. 메모이제이션을 하지 않은 재귀함수가 이런 형태를 가진다. |
조합 전체 탐색 |
| O(n!) | 팩토리얼 형태 | n의 팩토리얼 형태로 수행시간을 요구하며, 이 이상의 시간복잡도는 억지로 만들지 않는 한 볼 수 없다. | 순열 전체 탐색 |
