В
Дружище а ты вообще устройство хеш таблицы знаешь когда там этот худший случай будет
Size: a a a
2020 December 17
DM
А какая разница?
DM
Сложность не считается по удачным стечениям обстоятельств
В
А кто у тебя преподаватель был?)))
DM
Тоже хочешь подучиться?
В
Такой хуйне сорян нет
DM
Ну так не учи нубов фигне
В
Я вообще никого не учу, я просто скинул ссылку на Вики, каждый сам прочитает и поймет что ему надо
DM
Хеш таблицы не адресуют все элементы напрямую
DM
Так что там так или иначе будет какой-то перебор
DM
Просто не полный, но и не бинарный
DM
Но это не O(1)
DM
Хеш таблица тут разумный компромисс между сложностью и потреблением памяти
В
Ты вот давай эту хуйню кому нить другому рассказывай, а лучше прочитай
DM
Настоящий О(1) можно добиться только создав массив размером с максимальное число в исходных данных
DM
И адресовать ячейки по значению числа
DM
Но это не слишком эффективно по памяти
В
Это называется битовые поле и размер тебе нужен в 8 раз меньше
DM
Поэтому сказки про О(1) оставь для школьников
DM
Я тебе открою секрет, но O(n) тождественно O(n/8) в теории алгоритмов