Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 16
Это у вас не линейный поиск, это тот же самый бинарный поиск по В(+?)-дереву, где дерево задано в табличном виде, так что не выдумывайте велосипед ;)
Хм, а ведь и правда.
Но это «надо увидеть», а я проглядел:)
Но это «надо увидеть», а я проглядел:)
Вы не могли бы пояснить, где здесь B-дерево?
Как я понимаю, каждая клетка в таком случае есть узел дерева, а два его потомка — это две таблицы, которые останутся при ходе вверх и вправо.
Вроде похоже (если не заснул окончательно ещё:))
Вроде похоже (если не заснул окончательно ещё:))
Меня смущает, что при таком подходе потомки будут пересекаться. Или я что-то недопонял?
Как пишет ru.Вики:
В принципе, я здесь ничего дурного не вижу. Мы же не храним копии всех промежуточных массивов, и даже указатели не храним — мы их вычисляем по известному алгоритму. И пусть себе пересекаются на здоровье, проблем от этого не будет.
Каждый ключ имеет двух потомков — «левого» и «правого», как в бинарном дереве поиска. «Правый» потомок ключа является в то же время «левым» потомком следующего ключа.
В принципе, я здесь ничего дурного не вижу. Мы же не храним копии всех промежуточных массивов, и даже указатели не храним — мы их вычисляем по известному алгоритму. И пусть себе пересекаются на здоровье, проблем от этого не будет.
М… Данную схему легко развернуть на линейный список известного размера. Будем обращаться к элементу с индексом array[M*k+N], где k == sqrt(len(array)), дальше алгоритм строго так же применим.
(туплю, я алгоритм не так прочитал)
Осталось только написать процедуру быстрой сортировки массива в такую вот таблицу, и все — счастье.
Если вы быстро отсортируете массив в такую таблицу, то будете искать нужный элемент за C * sqrt(n).
Тогда как по отсортированному массиву — за C * log2(n). Так что счастье может и не наступить :)
Тогда как по отсортированному массиву — за C * log2(n). Так что счастье может и не наступить :)
А не нужно сортировать в таблицу. Этот алгоритм легко развернуть для линейного случая:
Пусть у нас есть вектор V с временем доступа к элементу o(1) и известной длиной len(V). Положим k=sqrt(len(V)).
введём переменные x,y такие, что p=y*k+x. Положим y=k-1,x=1. Осуществим проверку. Далее — либо мы делаем x+1, либо y-1. Дальше мы вычисляем p, это и есть номер элемента в массиве.
И не надо никаких таблиц.
Пусть у нас есть вектор V с временем доступа к элементу o(1) и известной длиной len(V). Положим k=sqrt(len(V)).
введём переменные x,y такие, что p=y*k+x. Положим y=k-1,x=1. Осуществим проверку. Далее — либо мы делаем x+1, либо y-1. Дальше мы вычисляем p, это и есть номер элемента в массиве.
И не надо никаких таблиц.
А можно пример какой-нибудь такой задачи где данные, удобно было бы хранить именно в такой отсорченой матрице?
Хм, я наверное чего то пропустил, но с каких пор O(log N) является «аутсайдером» по отношению к O(N)?
Даже если учесть, что во втором случае (который линейный) — N это совсем даже не N, а sqrt(N), то корень растет очень даже быстрее, чем логарифм
Ну или более формально
Даже если учесть, что во втором случае (который линейный) — N это совсем даже не N, а sqrt(N), то корень растет очень даже быстрее, чем логарифм
Ну или более формально
Тут дело в том, что элементы в матрице не просто отсортированы как один большой массив, а ОТДЕЛЬНО по каждой строке и ОТДЕЛЬНО (т.е. независимо от строк) по каждому столбцу.
Поэтому поиск нужно вести по каждой строке независимо от остальных, коих N штук, и это не просто O(N), а O(N * log(M)), так как в худшем случае придётся запускать N бинарных поисков.
Поэтому поиск нужно вести по каждой строке независимо от остальных, коих N штук, и это не просто O(N), а O(N * log(M)), так как в худшем случае придётся запускать N бинарных поисков.
Ну да, но в данном случае N и M — это как раз таки sqrt(N) — корень от настоящего размера массива данных. Опустим расходы на создание такой таблицы. Сложность O(sqrt(N) * log(sqrt(N))) — растет быстрее корня, который растет быстрее логарифма.
В статье по ссылке массив, отсортированный таким образом дается как вводная. Соответственно, приведенный алгоритм — оптимальный (ибо бинарный поиск все равно не будет работать, а на пересортировку массива для подготовки его к бинарному поиску уйдет больше времени, чем не только на этот алгоритм, но даже на простой линейный проход по всем элементам), меня смутило лишь записывание логарифмически сложного бинарного поиска в аутсайдеры для общего случая
В статье по ссылке массив, отсортированный таким образом дается как вводная. Соответственно, приведенный алгоритм — оптимальный (ибо бинарный поиск все равно не будет работать, а на пересортировку массива для подготовки его к бинарному поиску уйдет больше времени, чем не только на этот алгоритм, но даже на простой линейный проход по всем элементам), меня смутило лишь записывание логарифмически сложного бинарного поиска в аутсайдеры для общего случая
Так я не писал про общий случай, я писал «но иногда».
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Линейный алгоритм поиска в отсортированной таблице