Konstantni slovnik v C (Judy nebo neco jineho?)

[Pavel Kankovsky]

On Wed, 29 Jul 2009, Jan Kasprzak wrote:

> 	Trochu problem je, ze ja to mozna budu potrebovat na ruznych
> adresach (resp. nevim jestli bych umel nejak jeste v datech zaridit
> jednoznacnost adres v pripade pouziti vice takovych poli zaraz).

Ty adresy by se musely nějak předem rezervovat. Pokud předem nelze říct,
s jakou množinou datových souborů se bude pracovat, tak to ale bude 
poněkud obtížné, zejména ve 32 bitech.

Pokud by to nešlo, tak by se musely udělat datové struktury bez ukazatelů,
což nevím, zda nějaká knihovna umí.


On Wed, 29 Jul 2009, Dalibor Straka wrote:

> nas ve skole ucili, ze v takovem pripade lze udelat perfektni hashovani,
> kdy bude slozitost v nejhorsim pripade O(1).

O tom už tady vlastně byla jednou řeč. :)

Program, který ze vstupu přečte n bitů, dokáže rozlišit max. 2^n různých
vstupních hodnot. Proto platí, že program, který dokáže identifikovat
každý z N zadaných vstupů, musí přečíst v průměru \Omega(log N) bitů a
tedy provést \Omega(log N) operací, a to je zároveň dolní mez pro nejhorší
případ. (Konstantní složitost hašování je podmíněna předpokladem
konstantnosti operací s klíči a indexy nebo ukazateli.)


-- 
Pavel Kankovsky aka Peak                          / Jeremiah 9:21        \
"For death is come up into our MS Windows(tm)..." \ 21th century edition /