13 531
правка
Изменения
м
$O(n)$, соответственно, поиска частей одной последовательности в другой --- $O(m n)$,а поиска повторов в одной последовательности --- $O(n²)$.
Нет описания правки
* Об оптимизации поиска многомерных данных в распознавании}
* Филиппов В. В.
* Москва, ВМиК, кафедра ММП}
* В докладе рассматриваются методы оптимизации поиска многомерных повторов применительно к задачам распознавания, например, поиска неточных повторов в генетических последовательностях.
Смысл оптимизации очевиден --- он такой же, как и любого дерева поиска: свести
число сравнений с $O(n)$ до $O(log n)$, или точнее, в случае использования внешнейпамяти, $<m>O((k-1) log_k n)$</m>. Для пояснения: при использовании только оперативной памяти,
наиболее оптимальным деревом поиска является сбалансированное двоичное дерево,
так как количество сравнений элементов в нём будет равно $<m>O(log_2 n)$ </m> --- каждое
сравнение отсекает половину всего множества элементов. Однако в реальности базы данных,
как правило, имеют размер больший, чем оперативная память, и должны гарантированно сохранять
во внешней памяти, узким местом становится уже чтение с диска, а не проведение сравнений.
Это приводит к понятию «страницы» и логичной оптимизации дерева поиска --- увеличению
узла дерева до размера страницы, и созданию не 2 его дочерних узлов, а $k$, и,соответственно, $k$ подобластей.
Рассмотренные индексные структуры позволяют осуществлять поиск по окрестности заданного
вычислять последующие уже не нужно. Однако даже при такой оптимизации
сравнений сложность алгоритма поиска одного вектора всё равно остаётся равной
В то же время, если ввести использование простейшего K-D-дерева, оценка
сложности поиска вектора будет равна $<m>O(log_2 n)$</m>. Индексные структуры,
рассчитанные на внешнюю память, естественно, на небольших объёмах будут
медленнее именно потому, что используют внешнюю память, а не оперативную,