온라인 알고리즘, 오프라인 알고리즘

온라인 알고리즘이란 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘을 말합니다. 알고리즘 수행 중 새 입력을 받아 계산을 계속하기 때문에, 입력 전체가 메모리에 올라와 있지 않아도 계산을 시작할 수 있습니다.
오프라인 알고리즘이란 입력 전체를 이미 가지고 있다고 가정하고 동작하는 알고리즘입니다. 예를 들어 삽입 정렬은 새 원소를 이전의 정렬된 목록에 끼워넣는 방식으로 동작하므로, 처음에 모든 원소가 없더라도 정렬을 시작할 수 있습니다. 반면 선택 정렬은 남아 있는 모든 원소 중에서 최소의 원소를 찾아서 맨 앞에 옮기는 방식으로 동작하므로, 모든 원소를 알고 있어야만 동작을 시작할 수 있습니다. 따라서 삽입 정렬은 온라인 알고리즘, 선택 정렬은 오프라인 알고리즘이라고 할 수 있습니다.

참고문헌: 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제해결전략, 인사이트, (2012)