Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Задача обнаружения неизвестного повторяющегося фрагмента
(число повторов известно)
Эта задача редуцируется к следующей экстремальной задаче.
Дано: вектор Y Î RN, натуральные числа M, N–, N+,Tmin и Tmax.
Найти: набор (n1,...,nM) Î ΩM номеров такой, что
где Yn = (yn,...,yn+q-1), n = 0,...,N - q.
Задача NP-трудна. Обоснован приближенный алгоритм, имеющий временную сложность
O[M(N - q + 1)(Tmax - Tmin + q)] = O(MN2) = O(N3),
обоснован в [31].
Алгоритм, имеющий оценку временной сложности
O[q(q + M)(N - q + 1)(2l + 1) q-1] = O[N 3(2l) q-1]
и гарантирующий относительную погрешность решения задачи, не превышающую
(q - 1)/8l 2 ,
где l = l(N) – произвольная неограниченно растущая функция от N, предложен в [41].
|
предыдущая |
следующая |