RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Diskr. Mat., 2011, Volume 23, Issue 2, Pages 129–158 (Mi dm1148)  

This article is cited in 1 scientific paper (total in 1 paper)

Average complexity of searching for identical objects in random nonuniform databases

N. S. Kucherenko


Abstract: 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.

DOI: https://doi.org/10.4213/dm1148

Full text: PDF file (258 kB)
References: PDF file   HTML file

English version:
Discrete Mathematics and Applications, 2011, 21:3, 345–379

Bibliographic databases:

UDC: 519.2
Received: 13.10.2010
Revised: 07.02.2011

Citation: N. S. Kucherenko, “Average complexity of searching for identical objects in random nonuniform databases”, Diskr. Mat., 23:2 (2011), 129–158; Discrete Math. Appl., 21:3 (2011), 345–379

Citation in format AMSBIB
\Bibitem{Kuc11}
\by N.~S.~Kucherenko
\paper Average complexity of searching for identical objects in random nonuniform databases
\jour Diskr. Mat.
\yr 2011
\vol 23
\issue 2
\pages 129--158
\mathnet{http://mi.mathnet.ru/dm1148}
\crossref{https://doi.org/10.4213/dm1148}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2865914}
\elib{http://elibrary.ru/item.asp?id=20730391}
\transl
\jour Discrete Math. Appl.
\yr 2011
\vol 21
\issue 3
\pages 345--379
\crossref{https://doi.org/10.1515/DMA.2011.023}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79961078141}


Linking options:
  • http://mi.mathnet.ru/eng/dm1148
  • https://doi.org/10.4213/dm1148
  • http://mi.mathnet.ru/eng/dm/v23/i2/p129

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Kucherenko N.S., “Matematicheskoe ozhidanie srednei dliny kodov Khafmana”, Intellektualnye sistemy, 17:1-4 (2013), 241–245  mathscinet  elib
  • Дискретная математика
    Number of views:
    This page:249
    Full text:79
    References:38
    First page:16

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2019