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

В статье рассматриваются алгоритмы прямого и жадного синтеза минимального графа смежности. Проведен сравнительный статистический анализ времени работы указанных алгоритмов на основе вычислительных экспериментов со специально сгенерированными наборами входных данных. Для генерации тестовых данных был разработан алгоритм генерации нагрузок вершин графа смежности с заданными характеристиками. Результаты статистического анализа отношений скорости работы двух алгоритмов позволили выделить три поддиапазона мощности наборов вершин графов смежности: в поддиапазоне 5–35 жадный алгоритм работает существенно быстрее прямого, в поддиапазоне 60–105 прямой алгоритм работает существенно быстрее жадного, а в поддиапазоне 35–60 выигрыш в скорости зависит от конкретного набора данных. Кроме того, можно ожидать, что в диапазоне 5–60 будет обнаружено некоторое число статистических выбросов, сигнализирующих об особенностях в соответствующих наборах исходных данных.