40
правок
Изменения
→Алгоритм Хаффмана за O(n).
== Алгоритм Хаффмана за O(n)Описание алгоритма. ==
У нас есть массив частот (массив, в котором хранится число вхождений каждого символа в строку), отсортированный по возрастанию, нужно построить по нему код Хаффмана за <tex> O(n) </tex> (если массив не отсортирован, то это можно сделать, например,[[Цифровая_сортировка | цифровой сортировкой]] за <tex> O(n) </tex>, что не ухудшит асимптотику).
