Изменения

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

Сортировка Хана

27 байт добавлено, 20:12, 21 июня 2012
Нет описания правки
==Лемма №1==
Даны целые числа <tex>b</tex> <tex>\ge</tex> <tex>s</tex> <tex>\ge</tex> 0 , и <tex>T</tex> является подмножеством множества <tex>\{0, \ldots, 2^b - 1\}</tex>, содержащим <tex>n</tex> элементов, и <tex>t</tex> <tex>\ge</tex> <tex>2^{-s + 1}</tex>С<tex>^k_{n}</tex>. Функция <tex>h_{a}</tex> , принадлежащая <tex>H_{b,s}</tex> , может быть выбрана за время <tex>O(bn^2)</tex> так, что количество коллизий <tex>coll(h_{a}, T)</tex> <tex>\le</tex> <tex> t</tex>
==Лемма №2==
Анонимный участник

Навигация