시간복잡도
알고리즘의 성능을 나타내는 지표/알고리즘 수행 시간을 분석
시간복잡도는 낮으면 낮을수록 좋습니다.
시간복잡도를 측정하는 방법은 최선(best), 평균(average), 최악(worst)
시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
| 시간 복잡도 | N의 가용 범위 |
| O(N!) | 10 |
| O(2^N) | 20~25 |
| O(N^3) | 200~300 |
| O(N^2) | 3,000~5,000 |
| O(NlogN) | 100만 |
| O(N) | 1,000~2,000만 |
| O(logN) | 10억 이상 |
출처: 코딩테스트 합격자 되기 자바편
알고리즘 시간복잡도
| 삽입 | 이미 정렬된 파일에 새로운 레코드를 순서에 맞게 삽입하여 정렬 |
| 선택 | N개의 레코드 중 최소값을 찾아 첫번째에 배치, 나머지 N-1개의 레코드 중 최소값 찾아 두번째 배치, 이를 반복하여 정렬 |
| 버블 | 인접한 두 개의 레코드 키 값 비교 후 크기에 따라 레코드 위치 교환 |
| 퀵 | 자료 이동 최소화 후 하나의 파일을 부분적으로 나눠가면서 정렬 |
| 병합 | 이미 정렬된 2개의 파일을 한 개의 파일로 합병하여 정렬 |
| 셸 | 입력 파일을 매개변수 값으로 서브파일 구성후 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복 |
| 힙 | 완전 이진 트리를 이용한 정렬 |
| 정렬 | 최선의 경우(Best) | 평균(Average) | 최악의 경우(Worst) |
| 삽입 | O(n) | O(n²) | O(n²) |
| 선택 | O(n²) | O(n²) | O(n²) |
| 버블 | O(n²) | O(n²) | O(n²) |
| 퀵 | O(n log n) | O(n log n) | O(n²) |
| 병합 | O(n log n) | O(n log n) | O(n log n) |
| 셸 | O(n) | O(n^1.5) | O(n²) |
| 힙 | O(n log n) | O(n log n) | O(n log n) |
정렬 방법
1.삽입정렬(Insertion Sort)
- 두번째 숫자와 첫번째 숫자 비교하여 크기 순으로 정렬, 이후 3번째 숫자를 앞서 정렬된 숫자들 사이에 크기 순에 맞게 재정렬, 이를 반복
이미 정렬되어 있는 경우 O(n)
2.선택정렬(Selection Sort)
- 최소값을 찾아 첫번째 숫자와 위치 교환, 이후 정렬된 값을 제외한 최소 숫자를 정렬되지 않은 숫자 중 첫번째 숫자와 다시 위치 교환, 이를 반복
3.버블정렬(Bubble Sort)
- 왼쪽부터 인접한 두 숫자 간 크기 비교하여 위치 교환
-> 1Pass 마다 정렬되는 숫자들 중 가장 큰 숫자를 오른쪽으로 밀어서 배치
4.퀵정렬(Quick Sort)
자료 이동 최소화 후 하나의 파일을 부분적으로 나눠가면서 정렬
피벗(povot)이라는 요소가 존재합니다. 피벗이란 중심점이라는 뜻입니다. 중심축을 기준으로 왼쪽 리스트와 오른쪽 리스트로 나뉩니다.
피벗을 설정할 때는 리스트의 첫 번쨰 요소로 하던 가운데 요소로 하던 상관 없습니다. 여기에서는 첫 번째 요소로 하겠다는 가정으로 진행하겠습니다.
n, 2*n/2, 4*n/4, 8*n/8가 되어 O(n log n)의 시간복잡도를 가진다.
배열이 이미 정렬되어있는 경우 최악의 시간복잡도 O(n²)를 가진다. 배열에서 원소가 한개씩만 분리되어 순환 호출의 깊이가 N이 된다.
5.합병정렬/병합정렬(Merge Sort)2-way합병
이미 정렬된 2개의 파일을 한 개의 파일로 합병하여 정렬
6.셸 정렬
삽입정렬을 보완한 알고리즘이다.
셸 정렬은 삽입정렬의 단점인, 요소가 삽입될 위치가 멀리 떨어져 있을 경우 많은 이동이 필요한 점을 개선하기 위해 고안되었습니다. 셸 정렬은 일정 간격으로 나누어진 부분 리스트에 삽입정렬을 반복적으로 수행하여 원소의 이동 횟수를 줄입니다.
7.힙정렬
완전 이진 트리를 이용한 정렬
최대 힙의 삽입
1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.
아래의 최대 힙(max heap)에 새로운 요소 8을 삽입해보자.
2. 최대 힙(max heap)의 삭제
1.최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제된다.
최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것이다.
2.삭제된 루트 노드에는 힙의 마지막 노드를 가져온다.
3.힙을 재구성한다.
아래의 최대 힙(max heap)에서 최댓값을 삭제해보자
출처
- 꿈꾸는 라이언
'코테 > 알고리즘' 카테고리의 다른 글
| [JAVA/자바]플로이드 워셜 알고리즘 (Floyd-Warshall Algorithm) (0) | 2025.11.14 |
|---|---|
| [JAVA]Arrays.sort Lambda 정리 (0) | 2025.09.11 |
| [JAVA]위상정렬 알고리즘 (3) | 2025.08.13 |
| [Java] Stream()의 기초 문법 및 예시코드 (1) | 2025.06.26 |
| [SQL] 코딩 테스트 대비 SQL 문법 정리 (0) | 2025.03.06 |