Как сходна последовательность элементов в двух массивах

Question

У меня есть два массива. A содержит упорядоченный список элементов, таких как [e1, e2, e2, e3, e4, e5, e5]. B является подмножеством A с повторениями, такими как [e1, e1, e2, e5, e4]. На практике массивы будут больше этого (вероятно, длиной менее 10 000 элементов), и производительность имеет значение.

Как я могу количественно определить, насколько сходен порядок элементов в двух массивах? (В идеале без грубой форсировки сравнения)

Answer 1

Если вы хотите увидеть, насколько похожи две разные последовательности данных, учитывая, что может быть много повторных копий одних и тех же данных, вы можете проверить динамическое искажение времени , алгоритм, который измеряет эту величину. Он имеет приложения для распознавания речи, анализа данных временных рядов и сходства строк.

Answer 2

Во-первых, вам нужно убедиться, что каждый элемент B принадлежит A. Поскольку A является отсортированным массивом, это операция log(n) (с использованием бинарного поиска), которую нужно повторить максимум n раз, и что делает nxlog(n) операцию.

Во-вторых, вам нужно убедиться, что элементы B отсортированы, или посчитать количество перестановок, необходимое для их сортировки. Это снова операция nxlog(n) с использованием e.q. быстрая сортировка или любой другой эффективный алгоритм.