경쟁 분석(온라인 알고리즘)
Competitive analysis (online algorithm)경쟁 분석은 온라인 알고리즘을 분석하기 위해 고안된 방법으로, 온라인 알고리즘의 성능(예측할 수 없는 일련의 요청들을 충족해야 하며 미래를 볼 수 없는 상태에서 각 요청을 완료해야 함)을 최적의 오프라인 알고리즘의 성능과 비교한다.dvance. 알고리즘의 경쟁률(성능과 오프라인 알고리즘의 성능 사이의 비율)이 제한되어 있다면 알고리즘은 경쟁력이 있다."하드" 입력에 대해서만 알고리즘의 성능을 측정하는 기존의 최악의 경우 분석과 달리, 경쟁 분석에서는 "하드"와 "쉬움"이 최적의 오프라인 알고리즘의 성능에 의해 정의되는 하드 및 쉬운 입력 모두에 대해 알고리즘이 잘 수행되어야 한다.
많은 알고리즘에서 성능은 입력의 크기뿐만 아니라 입력값에도 좌우된다.예를 들어, 요소 배열을 정렬하는 것은 초기 순서에 따라 난이도가 다르다.그러한 데이터 의존 알고리즘은 평균 사례 데이터와 최악의 경우 데이터에 대해 분석한다.경쟁 분석은 일반적으로 데이터에 의존하는 온라인 및 랜덤화된 알고리즘에 대해 최악의 사례 분석을 수행하는 방법이다.
경쟁 분석에서, 사람들은 연구 중인 알고리즘과 어떤 최적의 알고리즘의 비용의 비율을 최대화하기 위해 의도적으로 어려운 데이터를 선택하는 "반복적"을 상상한다.무작위화된 알고리즘을 고려할 때, 그것에 대항하는 알고리즘에 의해 이루어진 무작위 선택에 대한 지식이 없는 망각적인 적과 그 실행 중 어느 시점에서든 알고리즘의 내부 상태에 대한 완전한 지식을 가진 적응적 적수를 더욱 구별해야 한다.(결정론적 알고리즘의 경우, 여기서 i.s 차이가 없다. 두 적대자는 단순히 알고리즘이 미래에 어떤 상태를 가져야 하는지를 계산하고, 그에 따라 어려운 데이터를 선택할 수 있다.
예를 들어, 퀵소트 알고리즘은 "피봇"이라고 불리는 한 요소, 즉 평균적으로 정렬되는 데이터의 중심 값에서 그리 멀지 않은 한 요소를 선택한다.그런 다음 Quicksort는 데이터를 두 개의 더미로 구분하는데, 하나는 피벗 값보다 값이 작은 모든 요소를 포함하고 다른 하나는 나머지 요소를 포함하고 있다.퀵소트가 어떤 결정론적 방식으로 피벗을 선택하는 경우(예를 들어, 항상 목록의 첫 번째 요소를 선택), 상대방은 퀵소트가 최악의 경우에 수행되도록 데이터를 미리 정렬하는 것이 쉽다.그러나 퀵소트가 어떤 무작위 요소를 피벗으로 선택할 경우, 어떤 무작위 숫자가 나오는지 모르는 적수는 퀵소트를 위한 최악의 경우 실행 시간을 보장하도록 데이터를 배열할 수 없다.
경쟁 분석(Sleator & Tarjan 1985년)을 통해 처음 분석된 고전적인 온라인 문제는 목록 업데이트 문제다.품목 리스트와 다양한 품목에 대한 일련의 요청이 주어질 경우, 리스트의 전면에 가까운 요소들이 접근하는 비용이 적게 드는 리스트에 대한 접근 비용을 최소화한다.(일반적으로 항목에 접근하는 비용은 리스트에서 그 위치와 동일하다.)접속 후, 리스트를 재배열할 수 있다.대부분의 재배치는 비용이 든다.Move-To-Front 알고리즘은 단순히 요청된 항목을 액세스 후 무료로 전면으로 이동시킨다.Transpose 알고리즘은 접근한 아이템을 그 직전에 아이템과 교환하기도 하며, 비용도 들지 않는다.고전적인 분석 방법들은 Transpose가 어떤 맥락에서 최적의 상태라는 것을 보여주었다.실제로 무브 투 프런트(Move-to-Front)는 훨씬 더 좋은 성능을 보였다.경쟁 분석은 적수가 최적의 알고리즘에 비해 임의로 나쁜 성능을 발휘하도록 만들 수 있는 반면, Move-To-Front는 결코 최적의 알고리즘의 두 배 이상의 비용을 발생시킬 수 없다는 것을 보여주기 위해 사용되었다.
서버의 온라인 요청의 경우, 미래에 대한 불확실성을 극복하기 위해 경쟁 알고리즘을 사용한다.즉, 알고리즘은 상상의 적수("경쟁자")가 "알고 있는" 반면, 미래를 "알고 있는" 것은 아니다.마찬가지로, 경쟁 알고리즘은 원격 위치에서 방금 일어난 일을 "알지" 않고 한 장소에 도착하는 요청에 알고리즘이 반응해야 하는 분산 시스템을 위해 개발되었다.이 설정은 (Awerbuch, Kutten & Peleg 1992)에서 제시되었다.
참고 항목
참조
- Sleator, D.; Tarjan, R. (1985), "Amortized efficiency of list update and paging rules", Communications of the ACM, 28 (2): 202–208, doi:10.1145/2786.2793.
- Aspnes, James (1998), "Competitive analysis of distributed algorithms", in Fiat, A.; Woeginger, G. J. (eds.), Online Algorithms: The State of the Art, Lecture Notes in Computer Science, vol. 1442, pp. 118–146, doi:10.1007/BFb0029567.
- Borodin, A.; El-Yaniv, R. (1998), Online Computation and Competitive Analysis, Cambridge University Press, ISBN 0-521-56392-5.
- Awerbuch, B.; Kutten, S.; Peleg, D. (1992), "Competitive Distributed Job Scheduling", ACM STOC, Victoria, BC, Canada.
