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