133
правки
Изменения
Отмена правки 60198 участника Alexandra Sannikova (обсуждение)
'''Сеть Бетчера''' (англ. ''Batcher bitonic mergesort'') {{---}} сортирующая сеть размером <tex>O(n \log^2n)</tex> и глубиной <tex>O(\log^2n)</tex>, где <tex>n</tex> {{---}} количество элементов для сортировки. Её авторство принадлежит Кену Бетчеру<ref>[http://en.wikipedia.org/wiki/Ken_Batcher Кену БетчеруWikipedia {{---}} Ken Batcher]</ref>.
В этой статье будет описана сортирующая сеть для случая когда <tex>n</tex> {{---}} степень двойки (<tex>n = 2^k</tex>).
Оценим размер сети. В объединяющей сети на <tex>n</tex> входов содержится <tex dpi="150">\frac{n \log_2{n}}{2}</tex> компараторов. Снова просуммируем формулу по числу объединяющих сетей и получим точную оценку <tex dpi = "150">\sum\limits^{\log_2{n}}_{i = 1}{ \frac{2^i \log_2{2^i}}{2} } = \sum\limits^{\log_2{n}}_{i = 1}{ 2^{i-1} i} = \frac{n \log_{2}^{2}{n} + 2 \log_2{n}}{4}</tex>.
==Примечания==
<references />
==Источники информации==
*[http://en.wikipedia.org/wiki/Bitonic_sorter Wikipedia {{---}} Bitonic mergesort]
