Big O 표기법
| O(1) | 데이터 크기에 무관하게 항상 일정한 시간이 걸리는 경우 -> 상수(constant) |
배열 인덱스 검색 |
| O(log n) | 데이터 크기가 2배 증가할 때 연산 수가 1단계씩 늘어나는 형태 -> 로그(logarithmic) |
이진검색 |
| O(n) | 입력(탐색할 데이터) 개수와 수행시간이 비례하는 경우 -> 선형 (linear) |
반복문, 선형 검색 |
| O(n log n) | N * log2 N 번만큼의 수행시간을 가짐 -> 선형로그(linear-logarithmic) |
증가 스텝이 2인 반복문, 병합정렬 |
| O(n^c) | 문제 해결 단계 수가 입력값 n제곱 -> 다차(polynomial) 형태 |
이중 for문, 버블정렬, 삽입정렬, 선택정렬 |
| O(C^n) | n이 증가할 때마다 걸리는 시간이 C배 증가 -> 지수(exponential) 형태 |
|
| O(n!) | 팩토리얼 형태 | 존재해서는 안됨 |
'Computer Science > Algorithm' 카테고리의 다른 글
| 버블 정렬 (Bubble Sort) + Java 구현 코드 (0) | 2025.01.21 |
|---|---|
| 이진 탐색 Binary Search + Java 코드 구현 (1) | 2025.01.20 |
| 선형 탐색 Linear Search + 보초법 + Java 구현 코드 (0) | 2025.01.20 |
| 재귀 Recursion - 재귀를 위한 점화식 Recurrence equation for recursion + 피보나치 수열 (0) | 2025.01.20 |
| 반복 Iteration - Counting method for iteration (1) | 2025.01.20 |