Geodesic
Average complexity of searching for identical objects in random nonuniform databases
Diskretnaya Matematika, Tome 23 (2011) no. 2, pp. 129-158.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper we study the average complexity of optimal algorithms solving the problem of searching for identical objects (PSIO) for random databases. We describe and investigate classes of PSIOs for which the average complexity as a function of the database volume grows logarithmically. For such classes of problems we find exact asymptotics of the complexity. We also study the case where the complexity of the optimal algorithm averaged over the class of problems is bounded and construct a class of PSIOs such that the average complexity of the optimal algorithm is an unbounded function growing slower than the logarithm. 
@article{DM_2011_23_2_a11,
     author = {N. S. Kucherenko},
     title = {Average complexity of searching for identical objects in random nonuniform databases},
     journal = {Diskretnaya Matematika},
     pages = {129--158},
     publisher = {mathdoc},
     volume = {23},
     number = {2},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2011_23_2_a11/}
}
TY  - JOUR
AU  - N. S. Kucherenko
TI  - Average complexity of searching for identical objects in random nonuniform databases
JO  - Diskretnaya Matematika
PY  - 2011
SP  - 129
EP  - 158
VL  - 23
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2011_23_2_a11/
LA  - ru
ID  - DM_2011_23_2_a11
ER  - 
%0 Journal Article
%A N. S. Kucherenko
%T Average complexity of searching for identical objects in random nonuniform databases
%J Diskretnaya Matematika
%D 2011
%P 129-158
%V 23
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2011_23_2_a11/
%G ru
%F DM_2011_23_2_a11
N. S. Kucherenko. Average complexity of searching for identical objects in random nonuniform databases. Diskretnaya Matematika, Tome 23 (2011) no. 2, pp. 129-158. http://geodesic.mathdoc.fr/item/DM_2011_23_2_a11/

[1] Gasanov E. E., Kudryavtsev V. B., Teoriya khraneniya i poiska informatsii, Fizmatlit, Moskva, 2002 | Zbl

[2] Kucherenko N. S., “Slozhnost poiska identichnykh ob'ektov v sluchainykh bazakh dannykh”, Intellektualnye sistemy, 11:1–4 (2007), 495–516 | MR

[3] Kucherenko N. S., “O promezhutochnykh funktsiyakh rosta slozhnosti poiska dlya sluchainykh baz dannykh”, Intellektualnye sistemy, 13:1–4 (2009), 361–395 | MR

[4] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, v. 1, 2, Mir, Moskva, 1967 | Zbl

[5] Knut D. E., Iskusstvo programmirovaniya, v. 3, Vilyams, Moskva, 2000

[6] Knuth D. E., “Optimum binary search trees”, Acta Informatica, 1 (1971), 14–25 | DOI | Zbl

[7] Gilbert E. N., Moore E. F., “Variable-length binary encodings”, Bell System Tech. J., 38 (1959), 933–968 | MR

[8] Garsia A. M., Wachs M. L., “A new algorithm for minimum cost binary trees”, SIAM J. Comput., 6 (1977), 622–642 | DOI | MR | Zbl