Optymalność niezależna od klucza

Optymalność niezależna od klucza jest właściwością niektórych struktur danych drzewa wyszukiwania binarnego w informatyce zaproponowanej przez Johna Iacono . Załóżmy, że pary klucz-wartość są przechowywane w strukturze danych i że klucze nie mają związku z ich sparowanymi wartościami. Struktura danych ma optymalność niezależną od klucza , jeśli przy losowym przypisywaniu kluczy oczekiwana wydajność struktury danych mieści się w stałym współczynniku optymalnej struktury danych. Optymalność niezależna od klucza jest związana z optymalnością dynamiczną .

Definicje

$binarnego$ , które mogą wyszukać sekwencję klawiszy ${\ Displaystyle X = x_ {1}, x_ {2}, \$ , gdzie każdy $displaystyle$ liczbą między $1}$ a ${\ displaystyle x_ {i}$ . Dla każdej sekwencji niech ${\ displaystyle X}$$być najszybszym algorytmem drzewa wyszukiwania$$kolejności$ elementy w . Niech ${\ displaystyle b}$ będzie jednym z $Displaystyle n!}$$wybrana$ \ $b (i)}$ permutacja sekwencji , gdzie ${\ displaystyle i}$ th wpis z ${\ displaystyle b}$ . Niech ${\ Displaystyle b (X) = b (x_ {1}), b (x_ {2}), \ cdots ,b(x_{m})}$ . $X$ dla sekwencji , że ${\ Displaystyle {\ textit {KIOPT}} (X) = E [{\ textit {OPT}} (b (X))]}$ .

$,$$wyszukać$ elementy w czasie

Związek z innymi granicami

Udowodniono, że optymalność niezależna od klucza jest asymptotycznie równoważna twierdzeniu o zbiorach roboczych . Wiadomo, że drzewa splay mają optymalność niezależną od klucza.