Реализация и время выполнения

Очевидно, что алгоритм Хаффмана может выполняться за полиномиальное время в зависимости от к — количества букв в алфавите. Рекурсивные вызовы алгоритма определяют серию к - 1 итераций по последовательно уменьшающимся алфавитам.
Каждая итерация, кроме последней, состоит из простого нахождения двух букв с наименьшей частотой и слияния их в одну букву с суммарной частотой. Даже

при простейшей реализации выявление букв с наименьшей частотой осуществля- ется за один проход по алфавиту с временем O(k), так что суммирование по к - 1 итерациям дает время O(k2).

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

С реализацией приоритетных очередей на базе кучи (см. главу 2) операции вставки и извлечения минимума выполняются за время О(log к); следовательно, каждая итерация, в которой выполняются всего три такие операции, выполняется за время О(log к). Суммирование по всем к итерациям дает общее время выполне- ния О(к log к).

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

Еще по теме Реализация и время выполнения:

  1. Вторая зрелость – время реализации своей мечты
  2. Статья 849. Права заказчика во время выполнения работы
  3. Статья 1196. Возмещение вреда, причиненного физическому лицу во время выполнения им договорных обязательств
  4. Время сейчас такое – время мудрости пришло!
  5. 14. 4. Рабочее время и время отдыха
  6. Зарубка на носу Дай время себе, дай время ребенку
  7. 3.3. Дальнейшая реализация проекта
  8. Глава 6. Реализация права
  9. 4.2. Реализация
  10. 4. Реализация прав по ипотеке
  11. 10. Реализация заложенного имущества
  12. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  13. Механизм реализации личности
  14. Практическая реализация.
  15. Статья 591. Реализация предмета залога
  16. Практическая реализация.
  17. Практическая реализация.