온라인 알고리즘: 두 판 사이의 차이

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

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

[[en:Online_algorithmOnline algorithm]]