Сложность алгоритма поиска совпадений в нескольких последовательностях

А. А. Грушо^a, М. И. Забежайло^a, В. В. Кульченков^b, Е. Е. Тимонина<sup>a

a</sup> Федеральный исследовательский центр «Информатика и управление» Российской академии наук
^b Банк ВТБ (ПАО)

Аннотация: Анализ данных на предмет наличия в них следствий неизвестной, но присутствующей причины возникает во многих задачах, и в работе приведен только один из примеров, связанный с поиском признаков мошенничества среди множества получателей потребительского кредита в банке. Для построения исходных данных был выбран метод, в котором признаки мошенничества проявляются в транзакционной активности после получения кредита, а именно: признаки основываются на том, каким образом выводятся полученные средства. Приведенный пример — частный случай ситуаций, когда в ограниченном множестве прецедентов данных, имеющих большую размерность, присутствуют и повторяются следствия одной причины. В этих условиях большое значение имеет задача нахождения повторения следствий. Построен алгоритм такого поиска, имеющий сложность меньше квадратичной. Сложность построенного алгоритма поиска всех повторений в $m$ упорядоченных последовательностях прецедентов не превосходит $mN$, где $N$ — длины все прецедентов. С учетом сложности упорядочения каждого прецедента и при исходной упорядоченности всего множества характеристик сложность решения задачи не превосходит $mN\log_2 N$.

Ключевые слова: сложность задачи классификации, машинное обучение, причинно-следственные связи, поиск повторений в наборе последовательностей.

Поступила в редакцию: 04.08.2025
Принята в печать: 15.10.2025

DOI: 10.14357/08696527250411