Задача
Во всех перечисленных примерах существует очень большое универсальное множество U возможных элементов: множество всех возможных людей, всех возможных абзацев (допустим, до определенной длины в символах) или всех воз- можных решений вычислительно сложной задачи. Структура данных организует хранение информации о множестве S ίΞ U, размер которого обычно составляет ничтожную часть U; при этом структура данных обеспечивает возможность встав- ки и удаления элементов из S, а также быстрой проверки того, принадлежит ли заданный элемент S.
Словарь представляет собой структуру данных, которая поддерживает следую- щие операции:
♦ MakeDictionary инициализирует словарь, способный хранить подмножество S универсального множества U; только что созданный словарь пуст.
♦ Insert(u) добавляет элемент u Uв множество S. Во многих случаях с u также связывается дополнительная информация (например, u может быть именем или табельным номером работника, а в структуре данных также сохраняется личная информация о работнике); будем считать, что эта информация сохра- няется в словаре как часть записи вместе с u. (Таким образом, в общем случае под «элементом u» будет пониматься u вместе с дополнительной информацией).
♦ Delete(u) удаляет элемент u из множества S, если он там хранится.
♦ Lookup(u) проверяет, принадлежит ли элемент u множеству S (и если принад- лежит читает дополнительную информацию, сохраненную вместе с u).
Многие реализации, рассмотренные ранее в книге, используют эти операции
(или часть из них): например, в реализациях алгоритмов обхода графа BFS и DFS велись множества S уже посещенных узлов. Тем не менее между теми задачами и текущей ситуацией существует принципиальное различие — размер U. Универ- сальное множество U в BFS и DFS представляет собой множество узлов V, уже явно заданное как часть входных данных. В таких случаях вполне допустимо хра- нить множество S !Ξ U так, как это делалось: определение массива с позициями |U|, по одной для каждого возможного элемента, и присваивание элементу в позиции, соответствующей u, 1 для u S или 0 для u ⅜ S. Такая реализация позволяет вы- полнять операции вставки, удаления и проверки с постоянным временем простым обращением к элементу массива.
С другой стороны, сейчас рассматривается ситуация, в которой универсальное множество U огромно. Это означает, что мы не сможем использовать массив, раз- мер которого хотя бы сопоставим с U. Принципиальный вопрос заключается в том, возможно ли в данном случае реализовать словарь, поддерживающий основные операции почти с такой же быстротой, как при относительно малых U.
Ответом на этот вопрос станет рандомизированный метод хеширования, опи- санный в следующем разделе. Нам не удастся достичь таких же характеристик, как в ситуации, в которой возможно определить массив по всему универсальному множеству U, но хеширование позволит подойти достаточно близко к ним.
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ