Исследователи факультета вычислительной математики и кибернетики МГУ разработали стохастическую модель для анализа временной сложности вычислительных алгоритмов, работающих с базами данных. Подход позволяет более реалистично оценивать поведение алгоритмов в условиях неопределённости и вариативности входных данных, характерных для практических вычислительных систем.

Результаты исследования опубликованы в Journal of Computer and Systems Sciences International.

Классические методы анализа временной сложности, как правило, опираются на детерминированные оценки и предполагают фиксированные сценарии выполнения алгоритмов. Однако при работе с базами данных и распределёнными системами на время выполнения существенно влияют случайные факторы: структура запросов, распределение данных, порядок доступа и особенности взаимодействия компонентов системы. В новой работе предложено учитывать эти факторы с помощью стохастических моделей.

Авторы рассматривают вычислительный процесс как случайный и описывают его через вероятностные характеристики времени выполнения. Такой подход позволяет получать не только асимптотические оценки, но и распределения времени работы алгоритмов, что даёт более точное представление о производительности систем в реальных условиях эксплуатации.

«Использование стохастических моделей позволяет более точно описывать временную сложность вычислительных задач в условиях взаимодействия с базами данных. Такой подход даёт возможность учитывать реальные сценарии работы вычислительных систем и оценивать их поведение не только в теории, но и в прикладных условиях», — отмечает Андрей Борисов, профессор кафедры математической статистики ВМК МГУ.

Предложенная модель может быть полезна при проектировании и оптимизации алгоритмов обработки данных, а также при анализе производительности информационных систем, где важны не только худшие или средние оценки, но и вероятность возникновения задержек. Результаты исследования представляют интерес для специалистов в области теории алгоритмов, анализа данных и разработки высоконагруженных вычислительных систем.