Средняя сложность поиска идентичных объектов для случайных неравномерных баз данных

В работе рассматривается поведение средней сложности оптимальных алгоритмов решения задачи поиска идентичных объектов (ЗПИО) для случайных баз данных. Описаны и исследованы классы ЗПИО, для которых функция роста средней сложности как функция от объема базы данных имеет логарифмический порядок роста. Для таких классов задач получены точные асимптотики функций роста. Изучен случай, когда сложность оптимального алгоритма в среднем по классу задач ограничена. Построен класс ЗПИО, для которого функция роста средней сложности оптимального алгоритма является неограниченной функцией по порядку меньшей логарифма.