Изменения

Перейти к: навигация, поиск

Обсуждение участника:KirillKutirev

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

Навигация