2025-11-12

오늘 배운 것

시간 복잡도

개념
- 알고리즘이 수행되는 데 걸리는 연산 횟수를 입력 크기 n에 대한 함수로 표현한 것
점근적 표기법
- 빅 오 : 최악
- 오메가 : 최선
- 세타 : 평균

분류

표기	예시	설명
O(1)	배열 인덱스 접근	입력 크기에 상관없이 일정
O(log n)	이진 탐색	입력을 절반씩 줄여나감
O(n)	단일 for문 탐색	입력 크기에 비례
O(n log n)	병합 정렬, 퀵 정렬 평균	효율적인 정렬 알고리즘
O(n²)	중첩 for문 (버블, 삽입정렬)	입력이 커질수록 급격히 증가
O(n³)	플로이드-워셜	3중 반복 구조
O(2ⁿ)	부분집합 탐색, 백트래킹	n이 20 넘어가면 비현실적
O(n!)	순열 생성, TSP 완전탐색	거의 실행 불가 수준

정렬
- stable : 같은 값을 가진 원소들의 기존 순서를 유지한 채 정렬
- In-place : 추가적인 메모리 공간을 거의 사용하지 않고 입력 배열 안에서 원소 직접 교환
| 알고리즘 | 최선 | 평균 | 최악 | Stable | In-place | 특징 요약 | | — | — | — | — | — | — | — | | Bubble Sort | O(n) | O(n²) | O(n²) | ✅ | ✅ | 인접 원소 교환 단순하지만 비효율적 | | Selection Sort | O(n²) | O(n²) | O(n²) | ❌ | ✅ | 매 단계 최소값 선택 교환 횟수 적음 | | Insertion Sort | O(n) | O(n²) | O(n²) | ✅ | ✅ | 거의 정렬된 배열에 유리 | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | ✅ | ❌ | 분할정복 기반 안정적 but 메모리 사용 | | Quick Sort | O(n log n) | O(n log n) | O(n²) | ❌ | ✅ | 평균적으로 빠르지만 피벗 선택 중요 | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | ❌ | ✅ | 힙 구조 활용 항상 일정한 성능 | | Counting Sort | O(n + k) | O(n + k) | O(n + k) | ✅ | ❌ | 정수 범위 제한 시 빠름 (비교정렬 아님) | | Radix Sort | O(d·(n + k)) | O(d·(n + k)) | O(d·(n + k)) | ✅ | ❌ | 자리수 단위 정렬 음수/소수엔 부적합 | | Tim Sort | O(n) | O(n log n) | O(n log n) | ✅ | ❌ | Python·Java 기본 정렬 (하이브리드형) |
1. Bubble Sort
```
 void bubbleSort(int[] arr) {
 	int n = arr.length;
 	for (int i = 0; i < n; i++) {
 		for (int j = 0; j < n - i - 1; j++) {
 			if (arr[j] > arr[j+1]) {
 				int tmp = arr[j];
 				arr[j] = arr[j+1];
 				arr[j+1] = tmp;
 			}
 		}
 	}
 }
```
  - 인접한 두 원소를 비교해 큰 값을 뒤로 보내며 반복해서 정렬한다.
  - 시간 복잡도
    - 최선 : O(n)
    - 평균 : O(n²)
    - 최악 : O(n²)
  - stable : O
  - In-place : O
  - 특징 : 단순하지만 느림, 거의 안씀
2. Selection Sort
```
 void selectionSort(int[] arr) {
 	int n = arr.length;
 	for (int i = 0; i < n - 1; i++) {
 		int minIdx = i;
 		for (int j = i + 1; j < n; j++) {
 			if (arr[j] < arr[minIdx]) minIdx = j;
 		}
 		int tmp = arr[minIdx];
 		arr[minIdx] = arr[i];
 		arr[i] = tmp;
 	}
 }
```
  - 매 단계에서 가장 작은(또는 큰) 값을 찾아 맨 앞으로 이동시킨다.
  - 시간 복잡도
    - 최선 : O(n²)
    - 평균 : O(n²)
    - 최악 : O(n²)
  - stable : X
  - In-place : O
  - 특징 : 교환 횟수는 적지만 비교 횟수는 많음
3. Insertion Sort
```
 void insertionSort(int[] arr) {
 	for (innt i = 1; i < arr.length; i++) {
 		int key = arr[i];
 		int j = i - 1;
 		while (j >= 0 && arr[j] > key) {
 			arr[j+1] = arr[j];
 			j--;
 		}
 		arr[j+1] = key;
 	}
 }
        
```
  - 이미 정렬된 구간에 새 원소를 올바른 위치에 삽입하며 정렬한다.
    - key 값보다 큰 원소들을 뒤로 미루고 작은 원소를 만나거나 맨 앞까지오면 그 때 멈춰서 그자리에 key를 넣기
  - 시간 복잡도
    - 최선 : O(n)
    - 평균 : O(n²)
    - 최악 : O(n²)
  - 특징: 거의 정렬된 배열에 매우 효율적 O(n)

2025-11-12

2025-11-12

오늘 배운 것

results matching ""

No results matching ""