Выполнять соединения в O (n) раз?

Question

есть ли способ объединить 2 таблицы в линейное время? Я слышал, что это можно сделать с помощью другой структуры данных (Hashtable), но я не уверен, как это можно сделать. Мне всегда было интересно, что объединение будет включать в себя перекрестный продукт, и поэтому это O (n ^ 2).

Answer 1

Алгоритм:

Перебрать таблицу A. Хэшировать все элементы, добавить их в массив Join.
Прокрутите таблицу B, проверьте каждый элемент, если он находится в хеш-таблице (Check - O (1)), если нет, добавьте в таблицу Join.

Answer 2

Вы можете объединить две таблицы, близкие к O (n), используя хеш-таблицу для поиска записей в одной таблице на основе идентификатора другой таблицы.

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

Поиск элемента в хеш-таблице - это не операция O (1), но она близка. С большим количеством данных у вас будет еще несколько коллизий хэшей, поэтому для некоторых поисков нужно выполнить более одного сравнения.

Answer 3

Зависит от типа объединения.Перекрестное соединение всегда будет O (n ^ 2), так как оно должно генерировать O (n ^ 2) записей.Равное соединение может быть выполнено с большей сложностью (O (n log (n))) или, возможно, даже амортизировано O (n)), при условии использования правильных структур данных.

Answer 4

Если для столбцов, используемых в объединении, доступны индексы, то они линейные, поскольку индексы допускают обратный порядок обеих таблиц. (Конечно, это не считая амортизированной стоимости индекса.)

Соединение хеш-функции будет линейным, хотя само хеширование не является бесплатным, а когда используемые ключи длинные, затраты также возрастают.

Answer 5

Основные поставщики БД давно устарели.Следовательно, объединение двух таблиц за время O (max (n, m)) на практике не имеет значения.Со стандартными индексами B-дерева сложность соединения составляет O (min (n, m) * log (max (n, m)).