АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Геометрическое хеширование

Читайте также:
  1. Геометрическое нивелирование
  2. Геометрическое решение биматричных игр 2x2.
  3. Основы теории гидродинамического подобия. Геометрическое, кинематическое и динамическое подобие явлений. Основные критерии подобия.
  4. Универсальное хеширование
  5. Уравнение Бернулли для потока жидкости. Геометрическое и энергетическое толкование
  6. Хеширование строк переменной длины

Геометрическое хеширование— широко применяемый в компьютерной графике и вычислительной геометрии метод для решения задач на плоскости или в трёхмерном пространстве, например для нахождения ближайших пар в множестве точек или для поиска одинаковых изображений. Хеш-функция в данном методе обычно получает на вход какое-либо метрическое пространство и разделяет его, создавая сетку из клеток. Таблица в данном случае является массивом с двумя или более индексами и называется файл сетки(англ. Grid file). Геометрическое хеширование также применяется в телекоммуникациях при работе с многомерными сигналами.[8]

Ускорение поиска данных

Хеш-таблицей называется структура данных, позволяющая хранить пары вида (ключ, хеш-код) и поддерживающая операции поиска, вставки и удаления элемента. Задачей хеш-таблиц является ускорение поиска, например, при записи текстовых полей в базе данных может рассчитываться их хеш код и данные могут помещаться в раздел, соответствующий этому хеш-коду. Тогда при поиске данных надо будет сначала вычислить хеш-код текста и сразу станет известно, в каком разделе их надо искать, то есть, искать надо будет не по всей базе, а только по одному её разделу (это сильно ускоряет поиск).

Бытовым аналогом хеширования в данном случае может служить помещение слов в словаре по алфавиту. Первая буква слова является его хеш-кодом, и при поиске мы просматриваем не весь словарь, а только нужную букву.

 

Пирамиды

Пирамида — двоичное дерево, в котором каждый родитель не меньше своих сыновей.

Пусть на основе входного массива нам удалось построить пирамиду. Тогда легко найти максимальный элемент (он находится в корне дерева). Этот элемент можно поместить в конец выходного массива, а в корень перенести последний из листьев.

Теперь нам нужно восстановить свойство пирамиды. Для этого меняем корень с наибольшим из его сыновей:

Однако свойство опять не выполнено. Поэтому опять меняем узел, для которого оно не выполнено, с наибольшим из его сыновей и повторяем эту операцию, пока не получим пирамиду:

Теперь мы опять можем взять максимум и поставить его в выходной массив на предпоследнее место и т.д.

Каждый такой шаг выполняется в худшем случае за время ~log2K, где K — кол-во элементов в пирамиде. Т. о. в худшем случае все шаги выполнятся за время log2N + log2(N-1) +... + log21, и т. к.

Nlog2N > log2N + log2(N-1) +... + log21 > log2(1*N) + log2(2*N) +... > N/2*log2N,

то время сортировки массива при уже построенной на его основе пирамиде есть O(Nlog2N).

Остаётся вопрос: как построить пирамиду?

Запишем элементы массива в узлы двоичного дерева по порядку. Начинаем проверять выполнение свойства пирамиды с предпоследнего уровня (для листьев оно, очевидно, выполнено). Если для какого-то узла свойство не выполнено, то опускаем его вниз по дереву, меняя его каждый раз с наибольшим из сыновей, пока для поддерева, в котором он был корнем, не будет выполнено свойство пирамиды.

Сколько времени займёт такая процедура? В худшем случае:

0*2k-1 + 1*2k-2 + 2*2k-3 +... + (i-1)*2k-i +... + 20*(k-1), где k — кол-во уровней в дереве (k~log2N).

Эту сумму (обозначим её S) можно посчитать двумя способами:

1) S = 2k-2 + 2k-3 +... + 1 + 2k-3 +... + 1 +... + 1 = (2k-1 - 1) + (2k-2 -1) +... + (2-1) = = 2k - 2 - (k -1) = 2k - k - 1; 2) S = 2S - S = 2k-1 + 2k-2 +... + 2 - (k-1) = = 2k - 2 - (k-1) = 2k - k - 1 ~ N - log2N - 1 ~ N

Таким образом, время построения пирамиды линейно, а значит время всего алгоритма сортировки ~Nlog2N.

Куча

Когда речь идёт о структуре данных, пирамиду обычно называют кучей.

Операции:

· построить из массива — за время O(N);

· взять максимум — O(1);

· удалить максимум и перестроить — O(log2N)

С помощью кучи можно быстро сделать частичную сортировку (например, переставить в конец массива несколько наибольших его элементов)


1 | 2 | 3 | 4 | 5 |

Поиск по сайту:

Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)