Обсуждение участника:KKutirev - История изменений

KKutirev: /* Алгоритм Хаффмана за O(n) . */

2013-12-07T19:46:56Z

‎Алгоритм Хаффмана за O(n) .

KKutirev: /* Алгоритм Хаффмана за O(n) . */

2013-12-07T19:39:05Z

‎Алгоритм Хаффмана за O(n) .

KKutirev: /* Алгоритм Хаффмана за O(n) . */

2013-12-07T19:32:48Z

‎Алгоритм Хаффмана за O(n) .

KKutirev: /* Алгоритм Хаффмана за O(n) . */

2013-12-07T19:29:41Z

‎Алгоритм Хаффмана за O(n) .

KKutirev: /* Алгоритм Хаффмана за O(n). */

2013-12-07T19:27:23Z

‎Алгоритм Хаффмана за O(n).

KKutirev: Алгоритм Хаффмана за O(n).

2013-11-26T19:30:22Z

Алгоритм Хаффмана за O(n).

Новая страница

== Алгоритм Хаффмана за O(n). ==

У нас есть массив частот, отсортированный по возрастанию, нужно построить по нему код Хаффмана за O(n).

Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума O(1), после чего в эту же очередь с приоритетами положить их сумму за O(1). У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Почему? Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге). Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее. У нас есть три варианта возможных пар минимумов. Первый: оба элемента из первого массива. Второй: первый элемент первого массива и первый элемент второго массива. И третий: два первых элемента второго массива. В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива. Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.

Итак, почему же этот алгоритм работает за линейное время? В алгоритме происходит ровно n итерации, так как на каждой итерации количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.

@@ Строка 3: / Строка 3: @@
 У нас есть массив частот, отсортированный по возрастанию, нужно построить по нему код Хаффмана за <tex> O(n) </tex> (но если массив не отсортирован, то это можно сделать цифровой сортировкой за  <tex> O(n) </tex> что не ухудшит решение).
-Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).  Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.
+Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).
 У нас есть три варианта возможных пар минимумов :

@@ Строка 3: / Строка 3: @@
 У нас есть массив частот, отсортированный по возрастанию, нужно построить по нему код Хаффмана за <tex> O(n) </tex> (но если массив не отсортирован, то это можно сделать цифровой сортировкой за  <tex> O(n) </tex> что не ухудшит решение).
-Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).  Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее. У нас есть три варианта возможных пар минимумов. Первый: оба элемента из первого массива. Второй: первый элемент первого массива и первый элемент второго массива. И третий: два первых элемента второго массива. В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива. Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.
+Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге).  Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее.
 В алгоритме <tex> n </tex> итерации, так как на каждой итерации количество элементов  уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.

← Предыдущая		Версия 19:32, 7 декабря 2013
Строка 5:		Строка 5:
	Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге). Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее. У нас есть три варианта возможных пар минимумов. Первый: оба элемента из первого массива. Второй: первый элемент первого массива и первый элемент второго массива. И третий: два первых элемента второго массива. В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива. Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.		Идея алгоритма заключается в том, чтобы создать такую очередь с приоритетами, из которой можно было бы доставать два минимума <tex> O(1) </tex>, после чего в эту же очередь с приоритетами положить их сумму за <tex> O(1) </tex>. У нас уже есть массив с отсортированными частотами, теперь давайте заведем второй массив, в котором мы будем хранить суммы. Несложно заметить, что в этом массиве элементы тоже будут идти по неубыванию. Допустим, что на каком-то шаге сумма получилась меньше чем предыдущая, но это противоречит тому, что на каждом шаге мы выбираем два минимальных (т.е. на каждом последующем шаге мы выбираем два минимума из элементов больших, чем на предыдущем шаге). Тогда на каждой итерации мы будет выбирать два минимума из четырех элементов (первые 2 элемента первого массива и первые 2 элемента второго массива). Теперь рассмотрим одну итерацию подробнее. У нас есть три варианта возможных пар минимумов. Первый: оба элемента из первого массива. Второй: первый элемент первого массива и первый элемент второго массива. И третий: два первых элемента второго массива. В первом варианте мы просто дописываем сумму в конец второго массива. Во втором варианте мы вычеркиваем первый элемент из второго массива и добавляем его сумму с первым элементом первого массива в конец второго. Ну и в третьем варианте, мы вычеркиваем два первых элемента второго массива и добавляем их сумму в конец этого массива. Если в первом массиве элементы закончились, а во втором осталось больше одного элемента, то они меняются ролями.

−	В алгоритме ~~происходит ровно~~ <tex> n </tex> итерации, так как на каждой итерации количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.	+	В алгоритме <tex> n </tex> итерации, так как на каждой итерации количество элементов уменьшается ровно на один, а минимум из 4-х элементов мы выбираем за константное время.

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

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