El análisis competitivo es un método inventado para analizar algoritmos en línea , en el que el rendimiento de un algoritmo en línea (que debe satisfacer una secuencia impredecible de solicitudes, completando cada solicitud sin poder ver el futuro) se compara con el rendimiento de un algoritmo fuera de línea óptimo. que puede ver la secuencia de solicitudes con antelación. Un algoritmo es competitivo si su ratio competitivo (la relación entre su rendimiento y el rendimiento del algoritmo fuera de línea) está acotado. A diferencia del análisis tradicional del peor de los casos, donde el rendimiento de un algoritmo se mide sólo para entradas "duras", el análisis competitivo requiere que un algoritmo funcione bien tanto en entradas difíciles como en entradas fáciles, donde "difícil" y "fácil" se definen por el rendimiento. del algoritmo óptimo fuera de línea.
Para muchos algoritmos, el rendimiento depende no sólo del tamaño de las entradas, sino también de sus valores. Por ejemplo, ordenar una serie de elementos varía en dificultad según el orden inicial. Estos algoritmos dependientes de los datos se analizan en busca de datos del caso promedio y del peor de los casos. El análisis competitivo es una forma de realizar análisis del peor de los casos para algoritmos aleatorios y en línea , que normalmente dependen de los datos.
En el análisis competitivo, uno imagina un "adversario" que elige deliberadamente datos difíciles para maximizar la relación entre el costo del algoritmo que se está estudiando y algún algoritmo óptimo. Al considerar un algoritmo aleatorio, se debe distinguir además entre un adversario ajeno , que no tiene conocimiento de las elecciones aleatorias realizadas por el algoritmo que se le enfrenta, y un adversario adaptativo que tiene pleno conocimiento del estado interno del algoritmo en cualquier momento durante su ejecución. . (Para un algoritmo determinista, no hay diferencia; cualquiera de los adversarios puede simplemente calcular qué estado debe tener ese algoritmo en cualquier momento en el futuro y elegir datos difíciles en consecuencia).
Por ejemplo, el algoritmo de clasificación rápida elige un elemento, llamado "pivote", que está, en promedio, no muy lejos del valor central de los datos que se están clasificando. Luego, Quicksort separa los datos en dos pilas, una de las cuales contiene todos los elementos con un valor menor que el valor del pivote y la otra contiene el resto de los elementos. Si Quicksort elige el pivote de alguna manera determinista (por ejemplo, eligiendo siempre el primer elemento de la lista), entonces es fácil para un adversario organizar los datos de antemano para que Quicksort funcione en el peor de los casos. Sin embargo, si Quicksort elige algún elemento aleatorio como pivote, entonces un adversario sin conocimiento de qué números aleatorios aparecen no puede organizar los datos para garantizar el peor tiempo de ejecución para Quicksort.
El problema clásico en línea analizado por primera vez con el análisis competitivo (Sleator y Tarjan 1985) es el problema de actualización de listas : dada una lista de elementos y una secuencia de solicitudes para los diversos elementos, minimice el costo de acceder a la lista donde se encuentran los elementos más cercanos. El acceso al frente de la lista cuesta menos. (Normalmente, el costo de acceder a un elemento es igual a su posición en la lista). Después de un acceso, la lista se puede reorganizar. La mayoría de los reordenamientos tienen un costo. El algoritmo Move-To-Front simplemente mueve el elemento solicitado al frente después del acceso, sin costo alguno. El algoritmo Transpose intercambia el elemento al que se accede con el elemento inmediatamente anterior, también sin costo. Los métodos de análisis clásicos demostraron que Transpose es óptimo en ciertos contextos. En la práctica, Move-To-Front funcionó mucho mejor. Se utilizó un análisis competitivo para mostrar que un adversario puede hacer que Transpose funcione arbitrariamente mal en comparación con un algoritmo óptimo, mientras que nunca se puede hacer que Move-To-Front incurra en más del doble del costo de un algoritmo óptimo.
En el caso de solicitudes en línea desde un servidor, se utilizan algoritmos competitivos para superar las incertidumbres sobre el futuro. Es decir, el algoritmo no "conoce" el futuro, mientras que el adversario imaginario (el "competidor") "sabe". De manera similar, se desarrollaron algoritmos competitivos para sistemas distribuidos, donde el algoritmo tiene que reaccionar a una solicitud que llega a una ubicación, sin "saber" lo que acaba de suceder en una ubicación remota. Este escenario fue presentado en (Awerbuch, Kutten y Peleg 1992).