토픽 92 / 92·비교표
메타휴리스틱과 병렬·확률 알고리즘
근사 알고리즘 vs 휴리스틱 vs 정확 알고리즘
| 항목 | 근사 알고리즘 | 휴리스틱 | 정확 알고리즘 |
|---|
| 보장 | 근사비 보장 (다항 시간) | 비보장 | 최적 보장 |
| 속도 | 빠름 (다항) | 매우 빠름 | 느림 (지수 가능) |
| 적용 | NP-hard 근사 | 실용적 최적화 | 소규모 정확 해 |
온라인 vs 오프라인 vs 스트리밍
| 항목 | 온라인 | 오프라인 | 스트리밍 |
|---|
| 입력 | 미래 모름 (순차) | 전체 입력 알려짐 | 대용량 순차 |
| 메모리 | 제한적 | 전체 | 매우 제한적 |
| 최적성 | 경쟁비로 평가 | 최적 가능 | 근사 |
| 적용 | 캐시 교체, 스케줄링 | 정렬, 경로 탐색 | 빈도 추정, 카디널리티 |
메타휴리스틱: GA vs SA vs PSO
| 항목 | GA (유전 알고리즘) | SA (담금질 기법) | PSO (입자 군집) |
|---|
| 해 구조 | 집단 (Population) | 단일 해 | 집단 (Swarm) |
| 탐색 | 진화 (교차/변이) | 담금질 (온도 감소) | 군집 이동 |
| 장점 | 범용/병렬화 | 구현 간단 | 연속 최적화 |
| 적용 | 조합 최적화 | 여행 외판원 | 함수 최적화 |
데이터 병렬 vs 태스크 병렬 vs 파이프라인
| 항목 | 데이터 병렬 | 태스크 병렬 | 파이프라인 |
|---|
| 분할 대상 | 데이터 | 작업 (함수) | 단계 |
| 연산 | 같은 연산 반복 | 다른 연산 | 단계별 연산 |
| 적용 | MapReduce, SIMD | 멀티스레드 | 영상 처리, 컴파일러 |
결정론적 vs Las Vegas vs Monte Carlo
| 항목 | 결정론적 | Las Vegas | Monte Carlo |
|---|
| 결과 | 항상 동일/정확 | 정확 (시간 확률적) | 근사 (정확도 확률적) |
| 시간 | 최악 보장 | 기대값 보장 | 보장 |
| 예시 | Dijkstra | 랜덤 퀵정렬 | 소수 판별 (Miller-Rabin) |