«Способы представления последовательностей, множеств, графов и деревьев»


Download 282.31 Kb.
bet2/7
Sana18.06.2023
Hajmi282.31 Kb.
#1560689
TuriСамостоятельная работа
1   2   3   4   5   6   7
Bog'liq
«Способы представления последовательностей, множеств, графов и д

Хеш-таблица — это обобщение способа хранения множества целых чисел (ключей) в форме вектора битов на случай, когда мощность универсума U очень велика по отношению к мощности множеств, с которыми нужно работать.
Хэш-функция — преобразует значения ключей к интервалу [0, m – 1], где m — размер хеш-таблицы,  Очевидно, что при этом каждому индексу хеш-таблицы будет соответствовать много различных значений ключей. Поэтому, во-первых, в хеш-таблице приходится хранить не биты, а сами значения ключей, а во-вторых, имеется возможность размещать в ней более одного ключа для каждого значения функции отображения (разрешать коллизии).
Если таблица построена правильно и не переполнена, то все функции (удаления, встатвки и тд) выполняются за постоянное время. В худшем случае (если коллизия - повторяющиеся элементы) - сложность линейная O(n).
Дерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся.
ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. имеет сложность O(log n) . Такую же сложность имеют операции вставки нового элемента в дерево и удаления
множеств А и B, КС=|С|;
  1. Краткая теория по графам


Мы будем рассматривать как ориентированные, так и нео­риентированные графы. Граф мы будем всегда обозначать G = (V,E), где V обозначает множество вершин, а Е — мно­жество ребер, причем Е  V X V для ориентированного графа и Е{{х,у}: х,у  V ۸ ху} для неориентированного графа. Будем также использовать обозначения |V| = n и |Е| = m.


Граф – совокупность точек, соединенных линиями. Точки называются вершинами, или узлами, а линии – ребрами, или дугами.


Download 282.31 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling