Каков порядок времени выполнения алгоритма с этим желаемым выводом?

Question

Есть N наборов Ai в An каждый со строковыми записями. Средний размер набора - К.

Для каждого Ai мы хотим вернуть список (или лучшую структуру данных?) Из N-1 наборов, исключая Ai, упорядоченный по тому, сколько элементов у них общего с Ai?

Пожалуйста, не стесняйтесь дать подробный ответ с хорошими математическими аргументами ...:)

Также это стандартная проблема, и я могу где-нибудь прочитать об этом?

Answer 1

По сути, вы генерируете каждый элемент списка результатов, выполняя пересечения из двух множеств.У вас есть N-1 пересечений в элементе списка результатов, который сводится к N-1 * IntersectTime.Для N элементов списка в результате получается сумма N (N-1) * IntersectTime.После этого вам нужно заказать N раз N-1 наборов, поэтому просто для их заказа у вас есть O (N² log N).

IntersectTime зависит от реализации набора, для типичного хэш-набора это для вас O(k).

Итак, наконец, у нас есть O (N²k) + O (N² log N) = O (N² (k + log N)) = (если мы предположим, что k> log N) O (N²k).

РЕДАКТИРОВАТЬ: когда вы действительно реализуете это, полезно знать, что, когда вы пересекаете два набора, вы можете использовать результат для 2 элементов списка результатов, что означает, что для первого у вас естьдля пересечения A_1 с N-1, для A_2 с N-2 (пересечение с A_1 уже было сделано для первого элемента), для A_3 с N-3 другими наборами и, наконец, для A_N без него.НО это не меняет время big-O, оно только вдвое сокращает время выполнения.

Answer 2

Вот моя попытка -

Полагаю, вы можете свести процесс к следующему: O (N * (C + S))

Где N - количество комплектов, C - это числоколичество времени, которое требуется для сравнения N-1 наборов, чтобы установить Ai, а S - количество времени, необходимое для сортировки N-1 наборов.

Сравнение составляет K элементов и K элементов N-1 раз, поэтому (N-1) K ^ 2 раза для сравнения

Сортировка должна занять лог (n - 1) времени с эффективнымАлгоритм Для простоты мы можем сократить N-1 до просто N

Итак, все должно работать за O (N (NK ^ 2 + log (N)))

Вы должны взятьэто с долей соли, я давно ничего не делал с алгоритмами.Также может быть более эффективный способ сравнения наборов.