Optimidad independiente de clave

La optimización independiente de la clave es una propiedad de algunas estructuras de datos de árboles de búsqueda binaria en informática propuesta por John Iacono . ^[1] Supongamos que los pares clave-valor se almacenan en una estructura de datos y que las claves no tienen relación con sus valores emparejados. Una estructura de datos tiene optimización independiente de la clave si, al asignar las claves aleatoriamente, el rendimiento esperado de la estructura de datos está dentro de un factor constante de la estructura de datos óptima. La optimización independiente de clave está relacionada con la optimización dinámica .

Definiciones

Hay muchos algoritmos de árbol de búsqueda binario que pueden buscar una secuencia de claves , donde cada una es un número entre y . Para cada secuencia , sea el algoritmo de árbol de búsqueda binario más rápido que busca los elementos en orden. Sea una de las posibles permutaciones de la secuencia , elegida al azar, donde está la enésima entrada de . Dejar . Iacono definió, para una secuencia , que . ${\displaystyle m}$ ${\displaystyle X=x_{1},x_{2},\cdots ,x_{m}}$ ${\displaystyle x_{i}}$ ${\displaystyle 1}$ ${\displaystyle n}$ ${\displaystyle X}$ ${\displaystyle {\textit {OPT}}(X)}$ ${\displaystyle X}$ ${\displaystyle b}$ ${\displaystyle n!}$ ${\displaystyle 1,2,\cdots ,n}$ ${\displaystyle b(i)}$ ${\displaystyle i}$ ${\displaystyle b}$ ${\displaystyle b(X)=b(x_{1}),b(x_{2}),\cdots ,b(x_{m})}$ ${\displaystyle X}$ ${\displaystyle {\textit {KIOPT}}(X)=E[{\textit {OPT}}(b(X))]}$

Una estructura de datos tiene optimización independiente de la clave si puede buscar los elementos en el tiempo . ${\displaystyle X}$ ${\displaystyle O({\textit {KIOPT}}(X))}$

Relación con otros límites

Se ha demostrado que la optimización independiente de clave es asintóticamente equivalente al teorema del conjunto de trabajo . Se sabe que los árboles splay tienen una optimización independiente de la clave.

Referencias

1. "John Iacono. Optimidad independiente clave. Algorithmica, 42(1):3-10, 2005" (PDF) . Archivado desde el original (PDF) el 13 de junio de 2010.