40
правок
Изменения
→Алгоритм Хаффмана за O(n) .
У нас есть три варианта возможных пар минимумов :
# Оба элемента из первого массива. В этом случае мы просто дописываем сумму в конец второго массива.# Первый элемент первого массива и первый элемент второго массива. В таком варианте вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго.# Два первых элемента второго массива.В такой ситуации вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива.
В алгоритме <tex> n </tex> итерации, так как на каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.
