disorder.ru

Интересно, есть ли алгоритм сортировки хуже чем ? Понятно, что алгоритм должен постоянно прогрессировать и гарантированно завершиться, то есть сортировка случайными или всевозможными перестановками не годится. Я что-то пока не могу придумать.

Обсуждали тут с коллегой за утренним кофе такую структуру данных как хеш. В процессе родилась задачка. Пусть есть хеш-таблица на 1000 ключей. В нее занесли n значений (n > 1000). В среднем на каждый ключ будет приходиться по n / 1000 коллизий. Значит, среднее время поиска значения будет O(1) + O(n / 1000) = O(n). Однако всем известно, что время поиска в хеш-таблице константа, т.е. O(1). Вопрос: где ошибка в рассуждениях?