Дальнейшие улучшения

Далее мы кратко рассмотрим естественную оптимизацию структуры данных Union-Find на базе указателей, приводящую к ускорению операций Find. Строго говоря, это улучшение не является необходимым для наших целей: для всех рас- сматриваемых применений структур данных Union-Find время О(log n) на операцию достаточно хорошо в том смысле, что дальнейшее улучшение времени операций не преобразуется в улучшение общего времени выполнения алгоритмов, которые их используют.
(Операции Union-Find не единственное вычислительное «узкое место» во времени выполнения этих алгоритмов.)

Чтобы понять, как работает улучшенная версия этой структуры данных, для начала рассмотрим «плохой» случай времени выполнения для структуры данных Union-Find на базе указателей. Сначала мы строим структуру, в которой одна из операций Find выполняется приблизительно за время log n. Для этого повторно выполняются операции Union для множеств равных размеров. Предположим, v — узел, для которого операция Find(v) выполняется за время log n. Теперь пред- ставьте, что Find(v) выполняется многократно, и каждое выполнение занимает время log n. Необходимость переходить по одному пути из log n указателей каждый раз для получения имени множества, содержащего v, оказывается лишней: после первого обращения Find(v) имя x множества, содержащего v, уже «известно»; также известно, что все остальные узлы, входящие в путь от v к текущему имени, тоже со- держатся в множестве x. Итак, в улучшенной реализации путь, отслеживаемый для каждой операции Find, «сжимается»: все указатели в пути переводятся на текущее имя множества. Потери информации при этом не происходит, а последующие опе- рации Find будут выполняться быстрее. Структура данных Union-Find и результат выполнения Find(v) с использованием сжатия изображены на рис.

4.13.

а


Ъ

Рис. 4.13. (а) Пример структуры данных Union-Find; (b) результат выполнения операции Find(v) с использованием сжатия пути



Теперь рассмотрим время выполнения операций для такой реализации. Как и преждее, операция Union выполняется за время 0(1), а операция MakeUnionFind(5) занимает время О(n) для создания структуры данных, представляющей множество размера n. Как изменилось время, необходимое для операции Find(v)? Некоторые операции Find по-прежнему занимают время до log n; для некоторых операций Find это время увеличилось, потому что после нахождения имени x множества, содер- жащего v, приходится возвращаться по той же цепочке указателей от v к x и пере- водить каждый указатель прямо на x. Но эта дополнительная работа в худшем случае удваивает необходимое время, а следовательно, не изменяет того факта, что операция Find выполняется за максимальное время О(log n). Выигрыш от сжатия путей проявляется при последующих вызовах Find, а для его оценки можно вос- пользоваться тем же методом, который был применен в (4.23): ограничением обще- го времени серии из n операций Find (вместо худшего времени одной операции). И хотя мы не будем вдаваться в подробности, серия из n операций Find со сжатием требует времени, чрезвычайно близкого к линейной зависимости от n; фактическая верхняя граница имеет вид О(nа(n)), где а(n) — очень медленно растущая функ- ция n, называемая обратной функцией Аккермана. (В частности, а(n) < 4 для любых значений n, которые могут встретиться на практике.)

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Дальнейшие улучшения:

  1. Статья 778. Улучшение нанимателем вещи, переданной в найм
  2. 3. Права и обязанности сторон в связи с улучшением арендованного имущества.
  3. 5.2.12. Укрепление и улучшение места (или мест), придающего уверенность
  4. Психологические аспекты улучшения работы по профилактике дорожно-транспортных нарушений.
  5. РАБОТА С ДАЛЬНИМИ СИГНАЛАМИ. ПВБ
  6. Тема 18. Правовые системы стран Дальнего Востока
  7. Глава четырнадцатая. Дальнейшие рекомендации по духовному очищению
  8. 3.3. Дальнейшая реализация проекта
  9. Е) ДАЛЬНЕЙШЕЕ ДВИЖЕНИЕ К ОРИГИНАЛЬНОМУ МЫШЛЕНИЮ
  10. 1.2. Изменения законодательства и дальнейшие планы
  11. II. 2. 7. Тетрады и дальнейшее разбиение множеств.
  12. Глава 10 Поощряйте его на дальнейшую учебу
  13. Дальнейшее развитие структуры средств массовой информации
  14. Тема 18. Правовые системы стран Дальнего Востока
  15. Зарубка на носу Дальнейшие указания в области наказания
  16. Тема восстановления и дальнейшего подъема народного хозяйства в советской прессе