Geodesic
The algorithm for identical object searching with bounded worst-case complexity and linear memory
Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 3-11.

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

We propose and investigate new algorithms permitting to find an identical object in the database using the number of operations not depending on the volume of the database. One algorithm requires memory size that depends linearly on the database volume in the average.
Keywords: key search, time complexity of algorithms, memory size. 
@article{DM_2016_28_2_a0,
     author = {\`E. \`E. Gasanov and A. M. Zubkov and N. V. Klykova},
     title = {The algorithm for identical object searching with bounded worst-case complexity and linear memory},
     journal = {Diskretnaya Matematika},
     pages = {3--11},
     publisher = {mathdoc},
     volume = {28},
     number = {2},
     year = {2016},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2016_28_2_a0/}
}
TY  - JOUR
AU  - È. È. Gasanov
AU  - A. M. Zubkov
AU  - N. V. Klykova
TI  - The algorithm for identical object searching with bounded worst-case complexity and linear memory
JO  - Diskretnaya Matematika
PY  - 2016
SP  - 3
EP  - 11
VL  - 28
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_2016_28_2_a0/
LA  - ru
ID  - DM_2016_28_2_a0
ER  - 
%0 Journal Article
%A È. È. Gasanov
%A A. M. Zubkov
%A N. V. Klykova
%T The algorithm for identical object searching with bounded worst-case complexity and linear memory
%J Diskretnaya Matematika
%D 2016
%P 3-11
%V 28
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_2016_28_2_a0/
%G ru
%F DM_2016_28_2_a0
È. È. Gasanov; A. M. Zubkov; N. V. Klykova. The algorithm for identical object searching with bounded worst-case complexity and linear memory. Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 3-11. http://geodesic.mathdoc.fr/item/DM_2016_28_2_a0/

[1] Gasanov E. E., Lugovskaya Yu. P., “Konstantnyi v khudshem sluchae algoritm poiska identichnykh ob'ektov”, Diskretnaya matematika, 11:4 (1999), 139–144 | DOI | MR | Zbl

[2] Klykova N. V., Bystrye algoritmy poiska ob'ektov v baze dannykh, Diplomnaya rabota, MGU, 2001, 13 pp.

[3] Gasanov E. E., “Reshenie problemy optimalnogo sinteza informatsionnykh grafov dlya bazovykh zadach poiska informatsii”, Doklady RAN, 374:4 (2000), 462–463 | MR

[4] Gasanov E.E., Kudryavtsev V.B., Teoriya khraneniya i poiska informatsii, Fizmatlit, M., 2002

[5] Gasanov E.E., Teoriya slozhnosti informatsionnogo poiska., Izd-vo MGU, M., 2005

[6] Knut D., Iskusstvo programmirovaniya dlya EVM. T. 3 Sortirovka i poisk, Mir, M., 1978 ; Knuth. D.E., The Art of Computer Programming. Volume 3. Sorting and searching, Addison-Wesley, 1973, 723 pp. | MR | Zbl | MR

[7] Borodin A. B., “Computational complexity — Theory and practice” (Currents in Theory of Computings), Prentice-Hall, Englewood Cliffs, NJ, 1973, 35–89 | MR

[8] Bottenbruch H., “Structure and use of ALGOL 60”, J. ACM, 9 (1962), 161–221 | DOI | MR | Zbl

[9] Dumey A., “Indexing for rapid random access memory systems”, Computers and Automation, 4:12 (1956), 6–9

[10] Maurer W. D., Lewis T. G., “Hash table methods”, Computing Surveys, 7 (1975), 5–20 | DOI

[11] Pletnev A.A., “Dinamicheskaya baza dannykh, dopuskayuschaya parallelnuyu obrabotku proizvolnykh potokov zaprosov”, Intellektualnye sistemy, 19:1 (2014), 117–142

[12] Pletnev A.A., “Logarifmicheskaya po slozhnosti parallelnaya obrabotka avtomatami proizvolnykh potokov zaprosov k dinamicheskoi baze dannykh”, Intellektualnye sistemy, 19:1 (2014), 171–212

[13] Pletnev A.A., “Informatsionno-grafovaya model dinamicheskikh baz dannykh i ee primenenie”, Intellektualnye sistemy, 18:1 (2014), 111–140 | MR

[14] Perper E. M., “Nizhnie otsenki vremennoi i ob'ëmnoi slozhnosti zadachi poiska podslova”, Diskretnaya matematika, 26:2 58–70 (2014) | DOI | MR

[15] Gasanov E.E., Efremov D.V., “Fonovyi algoritm resheniya dvumernoi zadachi o dominirovanii”, Intellektualnye sistemy, 18:3 (2014), 133–158

[16] Shutkin Yu.S., “Modelirovanie skhemnykh upravlyayuschikh sistem”, Intellektualnye sistemy, 18:3 (2014), 253–261 | MR

[17] Perper E.M., “Poryadok slozhnosti zadachi poiska v mnozhestve slov vkhozhdenii podslova”, Intellektualnye sistemy, 19:1 (2014), 99–116

[18] Ilin V.A., Sadovnichii V.A., Sendov Bl.Kh., Matematicheskii analiz. Prodolzhenie kursa / Pod red. A.N.Tikhonova, Izd-vo MGU, M., 1987, 358 pp. | MR