시간 복잡도와 Big-O 표기법
•
O(1): 상수 시간 – 해시 테이블 접근
•
O(log n): 이진 탐색
•
O(n): 선형 검색
•
O(n log n): 효율적인 정렬 알고리즘 (퀵, 머지 등)
•
O(n²): 중첩 반복문 – 버블 정렬
•
O(2ⁿ): 재귀 – 피보나치(메모이제이션 없을 때)
정렬 알고리즘 (Sorting)
알고리즘 | 평균 시간 | 특징 |
버블 정렬 | O(n²) | 인접한 두 값을 교환, 느림 |
선택 정렬 | O(n²) | 가장 작은 값을 선택 후 정렬 |
삽입 정렬 | O(n²) | 거의 정렬된 상태에 유리 |
퀵 정렬 | O(n log n) | 피벗 기준 분할, 평균 빠름 |
병합 정렬 | O(n log n) | 안정 정렬, 메모리 추가 필요 |
힙 정렬 | O(n log n) | 힙 자료구조 기반, in-place 정렬 |