Подмножество массива с использованием хеширования

Question

Проверить, является ли arr2 подмножеством. Входной сигнал: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1} Выход: arr2[] является подмножеством arr1[]

Если мы используем линейное зондирование. Hashtable будет выглядеть так: {0=7, 1=1, 2=13, 3=21, 4=3, 5=11} где первый элемент является индексом (хешированный код) вторым значением Если вы видите для элемента 7. Хэш-код - 7%6=1. Поэтому из 1 он должен пройти полную хэш-таблицу, проверив каждое ведро. Здесь Сложность времени - O (n)

Позже мы будем искать все элементы в arr2 с hashtable.

Таким образом, общая временная сложность будет равна Len (arr2) * O (n).

В чем преимущество хэширования?

Answer 1

Наилучшая ситуация поиска в хэш-таблице не O (n), а O (1). Поэтому в лучшем случае вы получите сложность Len (arr2) * O (1) => Len (arr2), и мы можем рассматривать ее как O (1). С другой стороны, наихудшая сложность - это действительно O (n). Итак, вы должны посмотреть на амортизированную стоимость всего алгоритма, который будет ниже, чем O (n)