온라인 알고리즘
온라인 알고리즘은 미래의 입력을 미리 알 수 없는 상태에서 현재까지 도착한 정보로 결정을 내리는 알고리즘이다. 알고리즘의 입력 처리 모델 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아...
| 분류 | 알고리즘 · 입력 처리 모델 |
|---|---|
| 목적 | 미래의 입력을 미리 알 수 없는 상태에서 현재까지 도착한 정보로 결정을 내리는 알고리즘 |
| 핵심 과정 | 요청이 순차적으로 도착할 때 즉시 처리하고 이전 선택을 변경할 수 있는지 여부를 모델에 명시한다 |
| 시간·연산 비용 | 문제별 시간·메모리와 경쟁비로 평가하며 단일한 공통 복잡도는 없다 |
| 적용 전제 | 요청 도착 순서와 버퍼 용량, 결정의 취소 가능성 등 온라인 모델이 정의되어야 한다 |
| 관련 분야 | 알고리즘 설계, 계산 복잡도 |
| 참고 자료 | MIT 알고리즘 강의 |
온라인 알고리즘은 미래의 입력을 미리 알 수 없는 상태에서 현재까지 도착한 정보로 결정을 내리는 알고리즘이다. 알고리즘의 입력 처리 모델 분야에서 다루며, 문제를 어떤 하위 단계로 표현하고 어떤 계산을 생략하거나 공유할지를 결정하는 방법이다. 이 기법을 적용할 때에는 결과의 정확성뿐 아니라 종료 조건, 필요한 상태의 표현과 입력 조건을 함께 정의한다.[1]
핵심 처리 과정은 다음과 같다. 요청이 순차적으로 도착할 때 즉시 처리하고 이전 선택을 변경할 수 있는지 여부를 모델에 명시한다. 경쟁 분석은 미래 정보를 모두 아는 최적 오프라인 해법과 비교한다. 설계 시에는 각 단계에서 보존되어야 할 불변식이나 조건을 정의하고, 결과를 반환하기까지 어떤 상태가 수정되는지를 추적한다.
계산 자원은 문제의 크기와 구현 방식에 좌우된다. 문제별 시간·메모리와 경쟁비로 평가하며 단일한 공통 복잡도는 없다. 적용 조건은 요청 도착 순서와 버퍼 용량, 결정의 취소 가능성 등 온라인 모델이 정의되어야 한다라는 점이다. 이 조건이 성립하는지를 먼저 확인해야 동일한 절차를 다른 입력에도 일관되게 사용할 수 있다.
캐시 교체, 작업 스케줄링, 네트워크 라우팅과 스트리밍 서비스에 쓰인다. 오프라인 알고리즘은 전체 입력을 미리 알고 처리한다. 실제 구현에서는 상태 표현, 자료구조 선택, 재귀 호출 또는 반복 처리, 메모리 접근과 경계 입력을 함께 고려한다. 이론적 계산 모델과 구체적인 프로그램의 시간·공간 비용은 입력 분포와 실행 환경에 따라 달라질 수 있다.[2]