63
правки
Изменения
Нет описания правки
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы.
Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных(т.е. на каждом последующем шаге мы выбираем два минимума из элементов не меньших, чем на предыдущем шаге).
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет <tex>O(n)</tex>.
==Псевдокод==
Код возвращает число бит, необходимых для кодирования текста с заданным количеством вхождений каждого символа.
'''int''' HuffmanCoding(a: '''int[0..n]'''):
b: '''int[0..n]'''
