Эта публикация цитируется в 2 статьях

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

Н. С. Кучеренко


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

УДК: 519.2

Статья поступила: 13.10.2010
Переработанный вариант поступил: 07.02.2011

DOI: 10.4213/dm1148

 Англоязычная версия: Discrete Mathematics and Applications, 2011, 21:3, 345–379

Реферативные базы данных:

• 
• 
•