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