온라인 알고리즘

전산학에서 온라인 알고리즘(online algorithm)이란 시작할 때 모든 입력 정보를 가지고 있지 않고, 입력을 차례로 받아들이면서 처리하는 알고리즘을 말한다. 이와는 반대로, 오프라인 알고리즘은 풀고자 하는 문제의 모든 데이터를 가지고 시작해야만 문제를 해결할 수 있다. 일례로, 선택 정렬은 정렬을 하기 전에 모든 데이터가 주어져야만 한다.

온라인 알고리즘은 기계 학습 분야에서 많이 연구된다.

예제

온라인 알고리즘의 다른 점을 다음과 같은 최단거리탐색 문제를 통해 생각해 본다. 탐색하고자 하는 그래프가 유한 개의 노드로 이루어졌다는 것은 알고 있으나 그 모든 연결 상태는 아직 알 수 없다고 하자. 그리고 알고리즘이 어떤 특정 노드에 도착했을 때만 그 주위에 연결된 이웃노드를 알게 된다. 이런 조건에서는 전체 상황을 알 수 없기 때문에 모든 가능한 경우를 나열하고 그 중에 최단거리를 얻어내는 것과 같은 간단한 방법이 없다. 그러므로 이런 경우를 위해 경쟁성 분석(competitive analysis)과 같은 새로운 알고리즘 성능 측정 방법이 필요하다.

같이 보기

• 실시간 컴퓨팅
• 경쟁성 분석
• 이집트 분수

참고 자료

• A. Borodin and R.El-Yaniv, Online Computation and Competitive Analysis Archived 2006년 10월 5일 - 웨이백 머신