알고리즘 | 간략설명 | 시간복잡도 |
---|---|---|
정렬 | ||
버블정렬 (bubble sort) | 앞쪽 부터 인접한 두 값을 비교하면서 정렬 하는 것을 반복해서 정렬. | O(n²) |
선택정렬 (selection sort) | 가장 작은 항목을 찾아서 맨앞부터 차례로 배치를 반복한다. | O(n²) |
삽입정렬 (insertion sort) | 배열의 앞쪽 부터 차례로 정렬되지 않은 값들을 앞쪽 정렬된 값과 비교해서 정렬한다. | O(n²) |
카운트정렬 (count sort) | 숫자의 발생횟수를 계산하는 누적 카운트 사용. 누적 카운트를 갱신해 순서대로 숫자를 직접배치 | O(n+k) |
병합정렬 (merge sort) | 리스트를 반으로 나누고, 각 리스트가 크기가 1이 될 때까지 반으로 나누면서 정렬 후 병합 안정적이고 대규모 데이터에서도 속도 빠름. | O(n log n) |
퀵정렬 (quick sort) | 피벗(리스트에서 기준이 되는 요소를 고르는 것)값의 선택이 성능에 큰 영향. 피벗값을 중심으로 작은값 리스트와, 큰값 리스트로 나눈다. | O(n log n) |
탐색 | ||
순차탐색 (sequential search) | 첫째 항목부터 차례로 비교한다. 배열이 정렬되어 있지 않을 경우 사용. | O(n/2) |
이진탐색 (binary search) | 정렬된 배열내에서 지정된 값의 위치를 찾는 과정을 반복한다. 중간요소 값보다 작으면 좌측에서 다시 찾고, 크면 우측에서 다시 찾고. 배열이 정렬되어 있는 경우 효과적 | O(log n) |