Optimalizace nezávislá na klíči - Key-independent optimality

Optimalita nezávislá na klíči je vlastností některých binární vyhledávací strom datové struktury v počítačová věda navrhl John Iacono.^[1]Předpokládejme to páry klíč – hodnota jsou uloženy v datové struktuře a že klíče nemají žádný vztah k jejich spárovaným hodnotám. Datová struktura má optimita nezávislá na klíči pokud je při náhodném přiřazení klíčů očekávaný výkon datové struktury v rámci konstantního faktoru optimální datové struktury. Souvisí to s optimitou nezávislou na klíči dynamická optimálnost.

Definice

Existuje mnoho algoritmů binárního vyhledávacího stromu, které mohou vyhledat sekvenci ${ displaystyle m}$klíče ${ displaystyle X = x_ {1}, x_ {2}, cdots, x_ {m}}$, kde každý ${ displaystyle x_ {i}}$je číslo mezi ${ displaystyle 1}$ a ${ displaystyle n}$Pro každou sekvenci ${ displaystyle X}$, nechť ${ displaystyle { textit {OPT}} (X)}$ být nejrychlejším algoritmem binárního vyhledávacího stromu, který vyhledává prvky v ${ displaystyle X}$ v pořádku. Nechat ${ displaystyle b}$ být jedním z${ displaystyle n!}$ možná permutace sekvence ${ displaystyle 1,2, cdots, n}$, vybráno náhodně, kde${ displaystyle b (i)}$ je ${ displaystyle i}$tého vstupu ${ displaystyle b}$.Nechat ${ displaystyle b (X) = b (x_ {1}), b (x_ {2}), cdots, b (x_ {m})}$. Iacono definováno, pro sekvenci ${ displaystyle X}$, že ${ displaystyle { textit {KIOPT}} (X) = E [{ textit {OPT}} (b (X))]}$.

Datová struktura má optimálně nezávislou na klíči, pokud může vyhledávat prvky v ${ displaystyle X}$ včas${ displaystyle O ({ textit {KIOPT}} (X))}$.

Vztah k jiným mezím

Ukázalo se, že optimálnost nezávislá na klíči je asymptoticky ekvivalentnívěta o pracovní sadě.Roztáhněte stromy je známo, že mají optimálnost nezávislou na klíči.

Reference