Algorithm (알고리즘)
- 알고리즘 : 어떠한 문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태
Big-O 표기법 : 알고리즘은 시간 복잡도 에 따라 분류할 수 있다.
O(1) : 상수형 복잡도
- 자료 크기와 무관하게 항상 같은 속도로 작동
- 알고리즘 수행 시간이 입력 데이터 수와 관계없이 일정
- 해시 함수(Hash Function)
O(log₂n) : 로그형 복잡도
- 문제를 해결하기 위한 단계의 수가 log₂n번만큼의 수행 시간을 가짐
- 이진 탐색(Binary Search)
O(n) : 선형 복잡도
- 입력 자료를 차례로 하나씩 모두 처리
- 수행 시간이 자료 크기와 정비례
- 순차 탐색(Sequential Search)
O(nlog₂n) : 선형 로그형 복잡도
- 문제를 해결하기 위한 단계의 수가 nlog₂n번만큼의 수행 시간을 가짐
- 퀵 정렬, 병합 정렬, 힙 정렬
O(n²)
- 제곱형 주요 처리 루프 구조가 2중인 경우
n크기가 작을 때에는 n²이 nlog₂n보다 빠를 수 있음
- 버블 정렬, 삽입 정렬, 선택 정렬
댓글남기기