An Entity of Type: software, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional worst-case analysis, where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm.

Property Value
dbo:abstract
  • Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional worst-case analysis, where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm. For many algorithms, performance is dependent not only on the size of the inputs, but also on their values. For example, sorting an array of elements varies in difficulty depending on the initial order. Such data-dependent algorithms are analysed for average-case and worst-case data. Competitive analysis is a way of doing worst case analysis for on-line and randomized algorithms, which are typically data dependent. In competitive analysis, one imagines an "adversary" which deliberately chooses difficult data, to maximize the ratio of the cost of the algorithm being studied and some optimal algorithm. When considering a randomized algorithm, one must further distinguish between an oblivious adversary, which has no knowledge of the random choices made by the algorithm pitted against it, and an adaptive adversary which has full knowledge of the algorithm's internal state at any point during its execution. (For a deterministic algorithm, there is no difference; either adversary can simply compute what state that algorithm must have at any time in the future, and choose difficult data accordingly.) For example, the quicksort algorithm chooses one element, called the "pivot", that is, on average, not too far from the center value of the data being sorted. Quicksort then separates the data into two piles, one of which contains all elements with value less than the value of the pivot, and the other containing the rest of the elements. If quicksort chooses the pivot in some deterministic fashion (for instance, always choosing the first element in the list), then it is easy for an adversary to arrange the data beforehand so that quicksort will perform in worst-case time. If, however, quicksort chooses some random element to be the pivot, then an adversary without knowledge of what random numbers are coming up cannot arrange the data to guarantee worst-case execution time for quicksort. The classic on-line problem first analysed with competitive analysis is the list update problem: Given a list of items and a sequence of requests for the various items, minimize the cost of accessing the list where the elements closer to the front of the list cost less to access. (Typically, the cost of accessing an item is equal to its position in the list.) After an access, the list may be rearranged. Most rearrangements have a cost. The Move-To-Front algorithm simply moves the requested item to the front after the access, at no cost. The Transpose algorithm swaps the accessed item with the item immediately before it, also at no cost. Classical methods of analysis showed that Transpose is optimal in certain contexts. In practice, Move-To-Front performed much better. Competitive analysis was used to show that an adversary can make Transpose perform arbitrarily badly compared to an optimal algorithm, whereas Move-To-Front can never be made to incur more than twice the cost of an optimal algorithm. In the case of online requests from a server, competitive algorithms are used to overcome uncertainties about the future. That is, the algorithm does not "know" the future, while the imaginary adversary (the "competitor") "knows". Similarly, competitive algorithms were developed for distributed systems, where the algorithm has to react to a request arriving at one location, without "knowing" what has just happened in a remote location. This setting was presented in. (en)
  • ( 경제학 용어에 대해서는 문서를 참고하십시오.) 경쟁성 분석은 온라인 알고리즘을 분석하기 위해 발명된 방법으로, (예측불가능한 요건들을 충족시켜야하는, 즉 미래를 보지 못하고 각각 주어진 요건을 해결해야하는)온라인 알고리즘의 성능과 (요건들을 미리 확인하는) 최적의 오프라인 알고리즘의 성능을 비교한다. 주어진 알고리즘은 그 알고리즘의 경쟁성 비율(competitive ratio)-온라인 알고리즘의 성능과 오프라인 알고리즘의 성능의 비율-가 제한(bounded)되어 있을 때 경쟁성이 있다고 말한다. 알고리즘의 성능이 "어려운" 입력으로만 측정되는 기존의 전통적인 wort-case analysis와 다르게, 경쟁성 분석에서는 알고리즘이 어려운 입력과 쉬운 입력 둘다에서 수행을 잘 해야한다. 이때 "어려움"과 "쉬움"은 최적의 오프라인 알고리즘의 성능으로 결정된다. 많은 알고리즘에서, 성능은 입력의 크기뿐만 아니라 이의 값에 좌우된다. 한 가지 예로 들 수 있는 것은 퀵 정렬 알고리즘이다. 이런 데이터-의존적인 알고리즘은 평균 케이스의 데이터와 최악의 케이스의 데이터에 대해서 분석된다. 경쟁성 분석은 온라인 알고리즘과 무작위 알고리즘의 최악의 케이스 분석을 하는 한 방법이며, 이 둘은 보통 데이터 의존적인 알고리즘이다. 경쟁성 분석에서는 일부러 어려운 데이터를 선택하는 '상대(adversary)'를 가정하여, 분석되고 있는 알고리즘과 최적의 알고리즘 간의 비용의 비율을 최대화한다. 가정되고 있는 '상대'는 알고리즘의 무작위적인 선택에 대한 지식이 전혀 없는 무지한 상대(oblivious adversary)와, 알고리즘이 어떻게 작동하는지에 대한 모든 지식을 비롯하여 알고리즘의 매 실행 시점마다의 내부 상태를 알고 있는 적응적인 상대(adaptive adversary)에 이르기까지 다양하다. 잊지 말아야할 점은, 이런 구분이 무작위 알고리즘에서만 의미있다는 것이다. 결정적인(deterministic) 알고리즘의 경우에는, 두 경우의 '상대' 모두 단순히 알고리즘이 각 미래 시간에 어떤 상태에 있어야 하는지 계산하고, 그에 맞는 어려운 데이터를 결정할 뿐이다. 예를 들어서, 퀵 정렬 알고리즘은 "중심점(pivot)"이라고 부르는 하나의 요소를 선택한다. 이것은 평균적으로, 정렬되고 있는 데이터의 중심으로부터 지나치게 멀지 않은 것이다. 그 후에 퀵 정렬 알고리즘은 데이터를 중심점보다 작은 데이터 무리와, 중심점보다 큰 데이터 무리로 나눈다. 만약 퀵 정렬 알고리즘이 중심점을 결정적인 방법으로 정한다면(예를 들어, 항상 리스트의 첫번째 요소 선택), 상대는 데이터를 미리 정렬하여 퀵 정렬이 최악의 시간(worst-case time)이 걸리도록 할 수 있다. 하지만 만약 퀵 정렬 알고리즘이 무작위로 요소를 골라 중심점으로 만든다면 상대는 무작위 숫자가 무엇인지에 대한 지식이 없으므로 퀵 정렬이 최악의 시간이 걸리도록 데이터를 바꿀 수 없다. 경쟁성 분석으로 처음 분석된 고전적인 온라인 알고리즘은 리스트 업데이트 문제(list update problem)이다. 아이템이 담긴 리스트와 아이템들에 대한 순차적인 요구가 주어졌을 때, 리스트의 앞부분에 가까울수록 접근에 대한 비용이 적은 것을 가정하고 리스트에 접근하는 비용을 최소화한다. (일반적으로, 아이템에 접근하는 비용은 아이템이 리스트에 있는 위치에 동일하다) 한번의 접근 후, 리스트는 재배열될 수 있다. 대부분의 재배열은 비용이 발생한다. 앞쪽으로 이동하는 알고리즘은 비용이 없이, 단순히 요청된 아이템을 접근 후 앞으로 옮긴다. 치환 알고리즘은 비용 없이 접근된 아이템과 그 바로 앞의 아이템을 바꾼다. 고전적인 분석 방법은 치환이 어떤 맥락에서는 최적이라는 것을 보여준다. 실제로는, 앞쪽으로 이동하는 알고리즘이 더 유용하다. 경쟁성 분석은 어떤 상대가 치환 알고리즘이 최적의 알고리즘에 비해 임의적인 정도까지 성능을 나쁘게 만들수 있음을 보이는데 사용되며, 반면 앞으로 이동하는 알고리즘은 최적의 알고리즘에 비해 두배 이상 성능을 나쁘게 만들 수 없다. 서버로부터 받은 온라인 리퀘스트의 경우, 경쟁적(competitive) 알고리즘들은 미래의 불확실성을 극복하기 위해 사용된다. 즉, 알고리즘은 미래에 대해서 알지 못하지만 가상의 상대("경쟁자")는 알고 있다. 비슷하게, 경쟁적 알고리즘들은 분산 시스템을 위해서ㄷ 개발되었는데, 여기서 알고리즘은 먼 장소에서 벌어진 일에 대해 알지 못한 채 어떤 장소로 도착하는 요청에 반응해야한다. (ko)
  • Em computação, a análise de complexidade de um algoritmo trata do estudo sobre os recursos consumidos pelos algoritmos ao executar sob diversas situações, como análise de pior cenário.Análise competitiva é um método criado para analisar algoritmos onlineen:online algorithm (que deve satisfazer uma sequencia imprevisível de requisitos, completando cada requisição sem prever o futuro). Nesta análise, a performance de um algoritmo online, é comparada à performance de um algoritmo ótimo offline que pode ver as sequencias de requisitos que seguirão. Um algoritmo é competitivo se sua razão de competitividade - a razão entre sua performance e da performance do algoritmo offline - é delimitado. Diferente da , onde a performance de um algoritmo é medida apenas por entradas "difíceis", análise competitiva requer que um algoritmo desempenhe bem em entradas fáceis e difíceis, onde "difícil" e "fácil" são definidos pela performance do algoritmo ótimo offline. Para muitos algoritmos, a performance depende não apenas do tamanho das entradas, mas também dos seus valores. Um exemplo disso é o algoritmo Quick sort, onde ordena uma cadeia de elementos. Esses algoritmos que dependem de dados são analisados por casos médios e pior caso. Análise competitiva é uma forma de fazer a análise de pior caso para um algoritmo online e , que tipicamente dependem da entrada. (pt)
dbo:wikiPageID
  • 8198743 (xsd:integer)
dbo:wikiPageLength
  • 5653 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1002299044 (xsd:integer)
dbo:wikiPageWikiLink
dbp:wikiPageUsesTemplate
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • Competitive analysis is a method invented for analyzing online algorithms, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal offline algorithm that can view the sequence of requests in advance. An algorithm is competitive if its competitive ratio—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional worst-case analysis, where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm. (en)
  • ( 경제학 용어에 대해서는 문서를 참고하십시오.) 경쟁성 분석은 온라인 알고리즘을 분석하기 위해 발명된 방법으로, (예측불가능한 요건들을 충족시켜야하는, 즉 미래를 보지 못하고 각각 주어진 요건을 해결해야하는)온라인 알고리즘의 성능과 (요건들을 미리 확인하는) 최적의 오프라인 알고리즘의 성능을 비교한다. 주어진 알고리즘은 그 알고리즘의 경쟁성 비율(competitive ratio)-온라인 알고리즘의 성능과 오프라인 알고리즘의 성능의 비율-가 제한(bounded)되어 있을 때 경쟁성이 있다고 말한다. 알고리즘의 성능이 "어려운" 입력으로만 측정되는 기존의 전통적인 wort-case analysis와 다르게, 경쟁성 분석에서는 알고리즘이 어려운 입력과 쉬운 입력 둘다에서 수행을 잘 해야한다. 이때 "어려움"과 "쉬움"은 최적의 오프라인 알고리즘의 성능으로 결정된다. (ko)
  • Em computação, a análise de complexidade de um algoritmo trata do estudo sobre os recursos consumidos pelos algoritmos ao executar sob diversas situações, como análise de pior cenário.Análise competitiva é um método criado para analisar algoritmos onlineen:online algorithm (que deve satisfazer uma sequencia imprevisível de requisitos, completando cada requisição sem prever o futuro). Nesta análise, a performance de um algoritmo online, é comparada à performance de um algoritmo ótimo offline que pode ver as sequencias de requisitos que seguirão. Um algoritmo é competitivo se sua razão de competitividade - a razão entre sua performance e da performance do algoritmo offline - é delimitado. Diferente da , onde a performance de um algoritmo é medida apenas por entradas "difíceis", análise compe (pt)
rdfs:label
  • Competitive analysis (online algorithm) (en)
  • 경쟁성 분석 (ko)
  • Análise competitiva (pt)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:knownFor of
is dbo:wikiPageDisambiguates of
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License