1
правка
Изменения
ошибка в алгоритме: выход за границу массива
# Два первых элемента второго массива.
Во всех случаях мы дописываем сумму в конец второго массива и передвигаем указатели в массивах на еще не использованные элементы. Докажем, что второй массив остается отсортированным по возрастанию после каждой итерации.
На каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время, поэтому асимптотика программы составляет <tex>O(n)</tex>.
'''int''' HuffmanCoding(a: '''int[0..n]'''):
b: '''int[0..n]'''
i, j, ans: '''int''' ''<font color=green>// i, j {{---}} указатели в массивах, inf {{---}} большое число</font>''
'''for''' k = 0 '''to''' n
b[k] = <tex>\infty</tex>
'''for''' k = 0 '''to''' n - 1
'''if''' a[i] + a[i + 1] <= a[i] + b[j] '''and''' a[i] + a[i + 1] <= b[j] + b[j + 1]//уже на 3-ей итерации выход за границу массива //i = 4, i + 1 = 5, a[5] = undefined
b[k] = a[i] + a[i + 1]
ans += b[k]
j += 2
'''return''' ans
==См. также==
*[[Оптимальное хранение словаря в алгоритме Хаффмана]]
