Какая сложность нахождения одинаковых ключей в двух множествах разной длины?

Question

Сложность нахождения одинаковых ключей в двух множествах в среднем случае O(min(n, m)), где n и m — размеры множеств. Это достигается за счет хэширования и проверки элементов меньшего множества на присутствие в большем.

YeaHub · Accepted Answer

Операция поиска пересечения двух множеств (set intersection) оптимизирована за счет использования хэш-таблиц. Вместо проверки всех возможных пар элементов используется принцип хэширования для быстрого поиска.Алгоритм работы:Берется меньшее множество для итерации по его элементамДля каждого элемента проверяется наличие в большем множествеПроверка выполняется за O(1) в среднем случае благодаря хэш-таблицеПример:set1 = {1, 2, 3, 4, 5}  # размер n = 5
set2 = {4, 5, 6, 7}     # размер m = 4

# Алгоритм возьмет set2 (меньшее) и проверит каждый элемент в set1
intersection = set1 & set2  # {4, 5}Сложность:Временная сложность: O(min(n, m))Пространственная сложность: O(k), где k — размер результата