El análisis competitivo es un método inventado para analizar algoritmos en línea , en el que se compara el rendimiento de un algoritmo en línea (que debe satisfacer una secuencia impredecible de solicitudes, completando cada solicitud sin poder ver el futuro) con el rendimiento de un algoritmo fuera de línea óptimo que puede ver la secuencia de solicitudes con anticipación. Un algoritmo es competitivo si su índice competitivo (el índice 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 solo para entradas "duras", el análisis competitivo requiere que un algoritmo funcione bien tanto en entradas duras como fáciles, donde "duras" y "fáciles" se definen por el rendimiento del algoritmo fuera de línea óptimo.
En el caso de muchos algoritmos, el rendimiento no solo depende del tamaño de las entradas, sino también de sus valores. Por ejemplo, la clasificación de una matriz de elementos varía en dificultad según el orden inicial. Estos algoritmos dependientes de los datos se analizan para obtener datos del caso promedio y del peor caso. El análisis competitivo es una forma de realizar un análisis del peor caso para algoritmos en línea y aleatorios , que normalmente dependen de los datos.
En el análisis competitivo, se imagina un "adversario" que elige deliberadamente datos difíciles para maximizar la relación entre el costo del algoritmo que se estudia y algún algoritmo óptimo. Al considerar un algoritmo aleatorio, se debe distinguir además entre un adversario inconsciente , que no tiene conocimiento de las elecciones aleatorias que hace 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 dos 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 quicksort elige un elemento, llamado "pivote", que, en promedio, no está demasiado lejos del valor central de los datos que se están ordenando. Quicksort luego 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 se ejecute en el peor tiempo posible. Sin embargo, si quicksort elige algún elemento aleatorio para que sea el pivote, entonces un adversario que no sepa qué números aleatorios están apareciendo no puede organizar los datos para garantizar un tiempo de ejecución en el peor de los casos 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 de los diversos elementos, minimice el costo de acceso a la lista donde los elementos más cercanos al principio de la lista cuesten menos para acceder. (Normalmente, el costo de acceder a un elemento es igual a su posición en la lista). Después de un acceso, la lista puede reorganizarse. La mayoría de las reorganizaciones tienen un costo. El algoritmo Move-To-Front simplemente mueve el elemento solicitado al frente después del acceso, sin costo. El algoritmo Transpose intercambia el elemento accedido con el elemento inmediatamente anterior, también sin costo. Los métodos clásicos de análisis mostraron que Transpose es óptimo en ciertos contextos. En la práctica, Move-To-Front funcionó mucho mejor. El análisis competitivo se utilizó para mostrar que un adversario puede hacer que Transpose funcione arbitrariamente mal en comparación con un algoritmo óptimo, mientras que Move-To-Front nunca puede incurrir en más del doble del costo de un algoritmo óptimo.
En el caso de las solicitudes en línea desde un servidor, se utilizan algoritmos competitivos para superar las incertidumbres sobre el futuro. Es decir, el algoritmo no "sabe" el futuro, mientras que el adversario imaginario (el "competidor") sí lo "sabe". De manera similar, se desarrollaron algoritmos competitivos para sistemas distribuidos, donde el algoritmo tiene que reaccionar a una solicitud que llega a un lugar, sin "saber" lo que acaba de suceder en un lugar remoto. Esta configuración se presentó en (Awerbuch, Kutten y Peleg 1992).