Какое худшее время выполнения для наиболее эффективного алгоритма построения дерева хаффмана?

Question

Я искал в Интернете везде и, похоже, не могу найти ответ на этот вопрос. Учитывая отсортированный список частот, каков наиболее эффективный алгоритм для создания дерева хаффмана и каков будет его большой O наихудший случай?

Answer 1

Если у вас есть список упорядоченных частот, то основной жадный алгоритм работает в линейном времени. Вы не можете победить это (с асимптотической точки зрения), так как вы должны обрабатывать каждый узел хотя бы один раз.