경쟁성 분석
경제학 용어에 대해서는 경쟁자 분석 문서를 참고하십시오.경쟁성 분석은 온라인 알고리즘을 분석하기 위해 발명된 방법으로, (예측불가능한 요건들을 충족시켜야하는, 즉 미래를 보지 못하고 각각 주어진 요건을 해결해야하는)온라인 알고리즘의 성능과 (요건들을 미리 확인하는) 최적의 오프라인 알고리즘의 성능을 비교한다. 주어진 알고리즘은 그 알고리즘의 경쟁성 비율(competitive ratio)-온라인 알고리즘의 성능과 오프라인 알고리즘의 성능의 비율-가 제한(bounded)되어 있을 때 경쟁성이 있다고 말한다. 알고리즘의 성능이 "어려운" 입력으로만 측정되는 기존의 전통적인 wort-case analysis와 다르게, 경쟁성 분석에서는 알고리즘이 어려운 입력과 쉬운 입력 둘다에서 수행을 잘 해야한다. 이때 "어려움"과 "쉬움"은 최적의 오프라인 알고리즘의 성능으로 결정된다.
많은 알고리즘에서, 성능은 입력의 크기뿐만 아니라 이의 값에 좌우된다. 한 가지 예로 들 수 있는 것은 퀵 정렬 알고리즘이다. 이런 데이터-의존적인 알고리즘은 평균 케이스의 데이터와 최악의 케이스의 데이터에 대해서 분석된다. 경쟁성 분석은 온라인 알고리즘과 무작위 알고리즘의 최악의 케이스 분석을 하는 한 방법이며, 이 둘은 보통 데이터 의존적인 알고리즘이다.
경쟁성 분석에서는 일부러 어려운 데이터를 선택하는 '상대(adversary)'를 가정하여, 분석되고 있는 알고리즘과 최적의 알고리즘 간의 비용의 비율을 최대화한다. 가정되고 있는 '상대'는 알고리즘의 무작위적인 선택에 대한 지식이 전혀 없는 무지한 상대(oblivious adversary)와, 알고리즘이 어떻게 작동하는지에 대한 모든 지식을 비롯하여 알고리즘의 매 실행 시점마다의 내부 상태를 알고 있는 적응적인 상대(adaptive adversary)에 이르기까지 다양하다. 잊지 말아야할 점은, 이런 구분이 무작위 알고리즘에서만 의미있다는 것이다. 결정적인(deterministic) 알고리즘의 경우에는, 두 경우의 '상대' 모두 단순히 알고리즘이 각 미래 시간에 어떤 상태에 있어야 하는지 계산하고, 그에 맞는 어려운 데이터를 결정할 뿐이다.
예를 들어서, 퀵 정렬 알고리즘은 "중심점(pivot)"이라고 부르는 하나의 요소를 선택한다. 이것은 평균적으로, 정렬되고 있는 데이터의 중심으로부터 지나치게 멀지 않은 것이다. 그 후에 퀵 정렬 알고리즘은 데이터를 중심점보다 작은 데이터 무리와, 중심점보다 큰 데이터 무리로 나눈다. 만약 퀵 정렬 알고리즘이 중심점을 결정적인 방법으로 정한다면(예를 들어, 항상 리스트의 첫번째 요소 선택), 상대는 데이터를 미리 정렬하여 퀵 정렬이 최악의 시간(worst-case time)이 걸리도록 할 수 있다. 하지만 만약 퀵 정렬 알고리즘이 무작위로 요소를 골라 중심점으로 만든다면 상대는 무작위 숫자가 무엇인지에 대한 지식이 없으므로 퀵 정렬이 최악의 시간이 걸리도록 데이터를 바꿀 수 없다.
경쟁성 분석으로 처음 분석된 고전적인 온라인 알고리즘은 리스트 업데이트 문제(list update problem)이다.[1] 아이템이 담긴 리스트와 아이템들에 대한 순차적인 요구가 주어졌을 때, 리스트의 앞부분에 가까울수록 접근에 대한 비용이 적은 것을 가정하고 리스트에 접근하는 비용을 최소화한다. (일반적으로, 아이템에 접근하는 비용은 아이템이 리스트에 있는 위치에 동일하다) 한번의 접근 후, 리스트는 재배열될 수 있다. 대부분의 재배열은 비용이 발생한다. 앞쪽으로 이동하는 알고리즘은 비용이 없이, 단순히 요청된 아이템을 접근 후 앞으로 옮긴다. 치환 알고리즘은 비용 없이 접근된 아이템과 그 바로 앞의 아이템을 바꾼다. 고전적인 분석 방법은 치환이 어떤 맥락에서는 최적이라는 것을 보여준다. 실제로는, 앞쪽으로 이동하는 알고리즘이 더 유용하다. 경쟁성 분석은 어떤 상대가 치환 알고리즘이 최적의 알고리즘에 비해 임의적인 정도까지 성능을 나쁘게 만들수 있음을 보이는데 사용되며, 반면 앞으로 이동하는 알고리즘은 최적의 알고리즘에 비해 두배 이상 성능을 나쁘게 만들 수 없다.
서버로부터 받은 온라인 리퀘스트의 경우, 경쟁적(competitive) 알고리즘들은 미래의 불확실성을 극복하기 위해 사용된다. 즉, 알고리즘은 미래에 대해서 알지 못하지만 가상의 상대("경쟁자")는 알고 있다. 비슷하게, 경쟁적 알고리즘들은 분산 시스템을 위해서ㄷ 개발되었는데, 여기서 알고리즘은 먼 장소에서 벌어진 일에 대해 알지 못한 채 어떤 장소로 도착하는 요청에 반응해야한다.[2]