Исследователи факультета вычислительной математики и кибернетики (ВМК) МГУ разработали стохастическую модель для анализа временной сложности вычислительных алгоритмов, работающих с базами данных. Подход позволяет более реалистично оценивать поведение алгоритмов в условиях неопределенности и вариативности входных данных, характерных для практических вычислительных систем.
Результаты исследования опубликованы в Journal of Computer and Systems Sciences International.
Классические методы анализа временной сложности, как правило, опираются на детерминированные оценки и предполагают фиксированные сценарии выполнения алгоритмов. Однако при работе с базами данных и распределенными системами на время выполнения существенно влияют случайные факторы: структура запросов, распределение данных, порядок доступа и особенности взаимодействия компонентов системы. В новой работе предложено учитывать эти факторы с помощью стохастических моделей.
Авторы рассматривают вычислительный процесс как случайный и описывают его через вероятностные характеристики времени выполнения. Такой подход позволяет получать не только асимптотические оценки, но и распределение времени работы алгоритмов, что дает более точное представление о производительности систем в реальных условиях эксплуатации.
«Использование стохастических моделей позволяет более точно описывать временную сложность вычислительных задач в условиях взаимодействия с базами данных. Такой подход дает возможность учитывать реальные сценарии работы вычислительных систем и оценивать их поведение не только в теории, но и в прикладных условиях», — отмечает Андрей Борисов, профессор кафедры математической статистики ВМК МГУ.
Предложенная модель может быть полезна при проектировании и оптимизации алгоритмов обработки данных, а также при анализе производительности информационных систем, где важны не только худшие или средние оценки, но и вероятность возникновения задержек. Результаты исследования представляют интерес для специалистов в области теории алгоритмов, анализа данных и разработки высоконагруженных вычислительных систем.
Информация предоставлена пресс-службой МГУ
Источник фото: ru.123rf.com
