Каков средний случай для функции поиска в хеш-таблице с коллизиями, разрешенными с помощью отдельной цепочки? В лучшем случае Θ (1), в худшем — is (n), но как насчет среднего случая? И как мне продемонстрировать сложность для среднего случая?
Это все еще O (1), предполагая, что реализация хеш-таблицы обеспечивает некоторый порог для size () / buckets, после которого он изменяет размеры (согласно std :: unordered map). Вы можете легко увидеть это — если вы искали каждый элемент в хеш-таблице, то среднее значение будет линейным кратным O (1), где этот линейный коэффициент равен коэффициенту загрузки выше …. Линейные факторы удаляются во время больших -О анализ.
Других решений пока нет …