Обсуждение участника:KirillKutirev — различия между версиями
(→Алгоритм Хаффмана за O(n) .) |
(→Алгоритм Хаффмана за O(n) .) |
||
| Строка 7: | Строка 7: | ||
У нас есть три варианта возможных пар минимумов : | У нас есть три варианта возможных пар минимумов : | ||
| − | # Оба элемента из первого массива. | + | # Оба элемента из первого массива. В этом случае мы просто дописываем сумму в конец второго массива. |
| − | # Первый элемент первого массива и первый элемент второго массива. | + | # Первый элемент первого массива и первый элемент второго массива. В таком варианте вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. |
| − | # Два первых элемента второго массива. | + | # Два первых элемента второго массива.В такой ситуации вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива. |
| − | + | Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями. | |
В алгоритме <tex> n </tex> итерации, так как на каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время. | В алгоритме <tex> n </tex> итерации, так как на каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время. | ||
Версия 16:48, 29 декабря 2013
Алгоритм Хаффмана за .
У нас есть массив частот (массив, в котором хранится число вхождений каждого символа в строку), отсортированный по возрастанию, нужно построить по нему код Хаффмана за (если массив не отсортирован, то это можно сделать, например, цифровой сортировкой за , что не ухудшит асимптотику).
Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума за , после чего в эту же очередь с приоритетами положить их сумму за . У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге). На каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.
У нас есть три варианта возможных пар минимумов :
- Оба элемента из первого массива. В этом случае мы просто дописываем сумму в конец второго массива.
- Первый элемент первого массива и первый элемент второго массива. В таком варианте вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго.
- Два первых элемента второго массива.В такой ситуации вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива.
Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.
В алгоритме итерации, так как на каждом шаге количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.
