Изменения

Перейти к: навигация, поиск

Алгоритм Хаффмана за O(n)

1279 байт добавлено, 01:59, 28 декабря 2017
Описание алгоритма
# Два первых элемента второго массива.
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы. Докажем, что второй массив остается отсортированным по возрастанию после каждой итерации.
Несложно заметитьТак как мы выбираем два элемента с наименьшими частотами <tex>f_1</tex> и <tex>f_2</tex>, то в силу выбора элементов их суммарная частота <tex>S = f_1 + f_2</tex> будет не больше суммы двух любых других из нерассмотренных частот, следовательно, никакая из последующих сумм не окажется меньше <tex>S</tex>. Докажем, что в этом массиве элементы тоже будут идти по неубыванию<tex>S</tex> не меньше значений, добавленных во второй массив на предыдущих итерациях. Допустим, что это не так и на каком-то шаге сумма получилась меньше чем предыдущаямы добавили в массив число <tex>S_1</tex> такое, что <tex>S_1 > S</tex>. Это значит, что на одной из итераций мы выбрали два элемента таким образом, что хотя бы один из них был больше <tex>f_1</tex> либо больше <tex>f_2</tex>. Но так как первый массив отсортирован по возрастанию, а второй изначально заполнен <tex>\infty</tex>, но это противоречит тому, что на каждом шаге каждой итерации мы выбираем два минимальных значения.е. на каждом последующем шаге мы выбираем два минимума Следовательно, наше предположение неверно, сумма <tex>S</tex> является наибольшей из элементов не меньших, чем на предыдущем шаге)рассмотренных ранее сумм и второй массив отсортирован по возрастанию.
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет <tex>O(n)</tex>.
Анонимный участник

Навигация