Независимая от ключа оптимальность - Key-independent optimality

Независимая от ключа оптимальность - свойство некоторых двоичное дерево поиска структуры данных в Информатика предложено Джон Яконо.^[1]Предположим, что пары ключ-значение хранятся в структуре данных, и что ключи не имеют отношения к их парным значениям. Структура данных имеет не зависящая от ключа оптимальность если при случайном назначении ключей ожидаемая производительность структуры данных находится в пределах постоянного коэффициента оптимальной структуры данных. Независимая от ключа оптимальность связана с динамическая оптимальность.

Определения

Существует множество алгоритмов бинарного дерева поиска, которые могут искать последовательность ${\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))]}$.

Оптимальность структуры данных не зависит от ключа, если она может искать элементы в ${\displaystyle X}$ во время${\displaystyle O({\textit {KIOPT}}(X))}$.

Связь с другими границами

Доказано, что оптимальность, не зависящая от ключа, асимптотически эквивалентнатеорема о рабочем множестве.Раскидистые деревья известно, что оптимальность не зависит от ключа.

Рекомендации

1. "Джон Иаконо. Независимая от ключа оптимальность. Algorithmica, 42 (1): 3-10, 2005" (PDF). Архивировано из оригинал (PDF) на 13.06.2010.