El análisis competitivo es un método inventado para analizar algoritmos online , en el que se compara el rendimiento de un algoritmo online (que debe satisfacer una secuencia impredecible de solicitudes, completando cada solicitud sin poder ver el futuro) con el rendimiento de un algoritmo offline óptimo. que puede ver la secuencia de solicitudes por adelantado. Un algoritmo es competitivo si su relación competitiva ( la relación entre su rendimiento y el rendimiento del algoritmo fuera de línea) está limitada. 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 difíciles como fáciles, donde "difícil" y "fácil" se definen por el rendimiento del algoritmo fuera de línea óptimo.
Para muchos algoritmos, el rendimiento depende no solo del tamaño de las entradas, sino también de sus valores. Por ejemplo, clasificar una serie de elementos varía en dificultad según el orden inicial. Dichos algoritmos dependientes de datos se analizan para obtener datos del caso promedio y del peor de los casos. El análisis competitivo es una forma de realizar el análisis del peor de los casos para algoritmos en línea y aleatorios , que generalmente 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, uno debe distinguir más entre un adversario ajeno , que no tiene conocimiento de las elecciones aleatorias hechas por el algoritmo enfrentado a él, 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", es decir, en promedio, no muy lejos del valor central de los datos que se ordenan. 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, siempre eligiendo el primer elemento de la lista), entonces es fácil para un adversario ordenar los datos de antemano para que quicksort funcione en el peor de los casos. Sin embargo, si quicksort elige algún elemento aleatorio para que sea el pivote, entonces un adversario sin conocimiento de los números aleatorios que se aproximan no puede organizar los datos para garantizar el peor tiempo de ejecución de quicksort.
El problema clásico en línea analizado por primera vez con análisis competitivo ( Sleator y Tarjan 1985 ) es el problema de actualización de la lista : dada una lista de elementos y una secuencia de solicitudes para los diversos elementos, minimice el costo de acceder a la lista donde los elementos se acercan más. el acceso al principio 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 puede reorganizarse. 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 de transposiciónintercambia el elemento accedido con el elemento inmediatamente anterior, también sin costo alguno. 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. Se utilizó el análisis competitivo para demostrar que un adversario puede hacer que Transpose funcione de manera arbitrariamente mala 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.