Problém předchůdce - Predecessor problem - Wikipedia

v počítačová věda, problém předchůdce zahrnuje údržbu a soubor položek na daný prvek efektivně dotaz který prvek předchází nebo následuje tento prvek v pořadí. Datové struktury slouží k řešení problému patří vyvážené binární vyhledávací stromy, van Emde Boas stromy, a fúzní stromy. V statický předchůdce problém, sada prvků se nemění, ale v problém dynamického předchůdce, vkládání do a mazání ze sady jsou povolena.^[1]

Problém předchůdce je jednoduchý případ nejbližší soused problém a datové struktury, které jej řeší, mají aplikace v problémech jako celočíselné třídění.

Definice

Problém spočívá v udržování sady $S$ , který obsahuje podmnožinu $U$ celá čísla. Každý z těchto celá čísla lze uložit pomocí a velikost slova z $w$ z čehož vyplývá, že ${ displaystyle U leq 2 ^ {w}}$ . Datové struktury, které problém řeší, podporují tyto operace:^[2]

předchůdce (x), který vrací největší prvek v $S$ menší nebo rovno $X$
nástupce (x), který vrací nejmenší prvek v $S$ větší nebo rovno $X$

Kromě toho datové struktury, které řeší dynamický verze problému také podporuje tyto operace:

vložte (x), který dodává $X$ do sady $S$
smazat (x), který odstraní $X$ ze sady $S$

Problém je obvykle analyzován v a transdichotomický model výpočtu jako slovo RAM.

Datové struktury

Rychlá trie x obsahující celá čísla 1 (001₂), 4 (100₂) a 5 (101₂), které lze použít k účinnému vyřešení předchozího problému.

Jedním z jednoduchých řešení tohoto problému je použití a vyvážený binární vyhledávací strom, které dosahuje (v Velká O notace ) a provozní doba z ${ displaystyle O ( log n)}$ pro dotazy předchůdce. The Van Emde Boas strom dosáhne doby dotazu ${ displaystyle O ( log log U)}$ , ale vyžaduje ${ displaystyle O (U)}$ prostor.^[1] Dan Willard navrhl vylepšení tohoto využití prostoru pomocí x-rychlá trie, což vyžaduje ${ displaystyle O (n log U)}$ prostor a stejný čas dotazu, a tím složitější y-rychlá trie, což vyžaduje pouze ${ displaystyle O (n)}$ prostor.^[3] Fúzní stromy, představil Michael Fredman a Willard, dosáhnout ${ displaystyle O ( log _ {w} n)}$ čas dotazu a ${ displaystyle O (n)}$ pro dotazy předchůdce pro statický problém.^[4] Dynamický problém byl vyřešen pomocí exponenciální stromy s ${ displaystyle O ( log _ {w} n + log log n)}$ čas dotazu,^[5] a s očekávaný čas ${ displaystyle O ( log _ {w} n)}$ použitím hashování.^[6]

Matematické vlastnosti

Bylo prokázáno několik pokusů dolní hranice na problém předchůdce nebo zjistit, jaká je doba chodu asymptoticky optimální řešení by byla. Například Michael Beame a Faith Ellen dokázal to pro všechny hodnoty $w$ , tady existuje hodnota $n$ s časem dotazu (v Velká Theta notace ) ${ displaystyle Omega left ({ tfrac { log w} { log log w}} right)}$ a podobně pro všechny hodnoty $n$ , existuje hodnota $n$ takový, že čas dotazu je ${ displaystyle Omega left ({ sqrt { tfrac { log n} { log log n}}} right)}$ .^[1] Mezi další důkazy nižších mezí patří pojem složitost komunikace.

Viz také

Reference

^ ^A ^b ^C Beame, Paul; Fich, Faith (Srpen 2002). „Optimální hranice pro problém předchůdce a související problémy“ (PDF). Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006 / jcss.2002.1822.
^ Rahman, Naila; Cole, Richard; Raman, Rajeev (17. srpna 2001). Optimalizované předchůdce datových struktur pro vnitřní paměť (PDF). Mezinárodní seminář o algoritmickém inženýrství. str. 67–78.
^ Willard, Dan (24. srpna 1983). "Log-logaritmické dotazy na nejhorší případy rozsahu jsou možné v prostoru Θ (n)". Dopisy o zpracování informací. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.
^ Fredman, Michael; Willard, Dan (1990). "Tryskání informační bariérou s fúzními stromy". Symposium on Theory of Computing: 1–7.
^ Andersson, Arne; Thorup, Mikkel (2007), „Dynamické uspořádané množiny s exponenciálními vyhledávacími stromy“, Deník ACM, 54 (3): A13, arXiv:cs / 0210006, doi:10.1145/1236457.1236460, PAN 2314255.
^ Raman, Rajeev (1996), „Prioritní fronty: malé, monotónní a transdichotomické“, Čtvrté výroční evropské symposium o algoritmech (ESA '96), Barcelona, Španělsko, 25. – 27. Září 1996, Přednášky v informatice, 1136, Berlín: Springer-Verlag, s. 121–137, doi:10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, PAN 1469229.

[Beame-1] A ^b ^C Beame, Paul; Fich, Faith (Srpen 2002). „Optimální hranice pro problém předchůdce a související problémy“ (PDF). Journal of Computer and System Sciences. 65 (1): 38–72. doi:10.1006 / jcss.2002.1822.

[Rahman-2] Rahman, Naila; Cole, Richard; Raman, Rajeev (17. srpna 2001). Optimalizované předchůdce datových struktur pro vnitřní paměť (PDF). Mezinárodní seminář o algoritmickém inženýrství. str. 67–78.

[Willard-3] Willard, Dan (24. srpna 1983). "Log-logaritmické dotazy na nejhorší případy rozsahu jsou možné v prostoru Θ (n)". Dopisy o zpracování informací. 17 (2): 81–84. doi:10.1016/0020-0190(83)90075-3.

[Fredman90-4] Fredman, Michael; Willard, Dan (1990). "Tryskání informační bariérou s fúzními stromy". Symposium on Theory of Computing: 1–7.

[5] Andersson, Arne; Thorup, Mikkel (2007), „Dynamické uspořádané množiny s exponenciálními vyhledávacími stromy“, Deník ACM, 54 (3): A13, arXiv:cs / 0210006, doi:10.1145/1236457.1236460, PAN 2314255.

[6] Raman, Rajeev (1996), „Prioritní fronty: malé, monotónní a transdichotomické“, Čtvrté výroční evropské symposium o algoritmech (ESA '96), Barcelona, Španělsko, 25. – 27. Září 1996, Přednášky v informatice, 1136, Berlín: Springer-Verlag, s. 121–137, doi:10.1007/3-540-61680-2_51, ISBN 978-3-540-61680-1, PAN 1469229.

[1]

[2]

[3]

[4]

[5]

[6]