온라인 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

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

예제[편집]

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

같이 보기[편집]

참고 자료[편집]