Optimalidad independiente de clave

La optimización independiente de la clave es una propiedad de algunas estructuras de datos de árboles de búsqueda binarios en informática propuesta por John Iacono . ^[1] Suponga 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 una optimización independiente de la clave si, al asignar aleatoriamente las claves, 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 la clave está relacionada con la optimización dinámica .

Hay muchos algoritmos de árbol de búsqueda binaria 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 sucesión , elegida al azar, donde es la enésima entrada de . deja _ Iacono definió, para una secuencia , que . ${\ estilo de visualización m}$ $X=x_{1},x_{2},\cdots,x_{m}$ ${\ estilo de visualización x_ {i}}$ ${\ estilo de visualización 1}$ ${\ estilo de visualización n}$ ${\ estilo de visualización X}$ ${\textit {OPT}}(X)$ ${\ estilo de visualización X}$ ${\ estilo de visualización b}$ ${\ estilo de visualización n!}$ $1,2,\cdots,n$ ${\ estilo de visualización b (i)}$ ${\ estilo de visualización i}$ ${\ estilo de visualización b}$ $b(X)=b(x_{1}),b(x_{2}),\cdots,b(x_{m})$ ${\ estilo de visualización X}$ ${\textit {KIOPT}}(X)=E[{\textit {OPT}}(b(X))]$

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

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