온라인 알고리즘

    
        온라인 알고리즘 이란 무엇입니까?
        
        온라인 알고리즘 (online algorithm) 이라는 것은 시작할 때
        
        입력을 차례로 받아들이면서 처리하는 알고리즘을 말합니다.
        
        이 알고리즘은 기계학습 분야에서 많이 쓰입니다.
        
        
        이와는 반대로, 오프라인 알고리즘 이라는 것이 있습니다.
        
        오프라인 알고리즘은 시작할 때 데이터를 다 알고 있어야만 
        
        문제를 풀 수 있는 그런 알고리즘 입니다.
        
        
        예를 들어 보면 선택 정렬은 정렬을 하기 전에 데이터가 다 
        
        주어져야만 합니다. 
    
        온라인 알고리즘은 기계 학습 분야에서 많이 연구됩니다.
        
        
        온라인 알고리즘의 필요성을 거리 탐색 문제를 통하여 
        
        생각해 볼 수 있을 것입니다.
        
        탐색 하려는 그래프가 기껏해야 유한 개의 노드로 이루어졌다는
        
        것은 알고 있으나 그 연결 상태들을 다 알 수 없다고 합시다. 
        
        그리고 그 알고리즘이 어떤 특정 노드에 도착했을 때에만 
        
        그 주위에 링크된 이웃 노드들을 알 수 있다 합시다. 
        
        이러한 조건에서 가장 짧은 거리를 찾는 방법은 매우 어려울
        
        뿐만 아니라 가능한 경우들을 다 나열한 다음에 그 중에서 
        
        가장 짧은 거리를 찾는 그런 방법으로는 찾을 수가 없을 것입니다. 
        
        즉, 경쟁성 분석(competitive analysis)과 같은 새로운 알고리즘이 필요합니다.