«Способы представления последовательностей, множеств, графов и деревьев»
Download 282.31 Kb.
|
«Способы представления последовательностей, множеств, графов и д
- Bu sahifa navigatsiya:
- Дерево двоичного поиска (ДДП)
Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U очень велика по отношению к мощности множеств, с которыми нужно работать.
Хэш-функция — преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы, Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, имеется возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии). Если таблица построена правильно и не переполнена, то все функции (удаления, встатвки и тд) выполняются за постоянное время. В худшем случае (если коллизия - повторяющиеся элементы) - сложность линейная O(n). Дерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся. ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. имеет сложность O(log n) . Такую же сложность имеют операции вставки нового элемента в дерево и удаления множеств А и B, КС=|С|; Краткая теория по графамМы будем рассматривать как ориентированные, так и неориентированные графы. Граф мы будем всегда обозначать G = (V,E), где V обозначает множество вершин, а Е — множество ребер, причем Е V X V для ориентированного графа и Е{{х,у}: х,у V ۸ ху} для неориентированного графа. Будем также использовать обозначения |V| = n и |Е| = m. Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами. Download 282.31 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling