Ключонезависимая оптимальность

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

Определения

Существует множество алгоритмов двоичного дерева поиска, которые можно найти последовательность $m$ ключи $X=x_{1},x_{2},\cdots ,x_{m}$, где каждый $x_{i}$ это число между $1$ и $n$. Для каждой последовательности $X$, позволять ${\textit {OPT}}(X)$ быть самым быстрым алгоритмом двоичного дерева поиска, который ищет элементы в $X$ чтобы. Позволять $b$ быть одним из $n!$ возможный перестановка последовательности $1,2,\cdots ,n$, выбранный случайно, где $b(i)$ это $i$ая запись $b$. Позволять $b(X)=b(x_{1}),b(x_{2}),\cdots ,b(x_{m})$. Яконо определил для последовательности $X$, что ${\textit {KIOPT}}(X)=E[{\textit {OPT}}(b(X))]$.

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

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

Доказано, что независимая от ключа оптимальность асимптотически эквивалентна тот Теорема о рабочем множестве . Известно, что деревья расширения обладают ключевой оптимальностью.