Как повысить эффективность

Question

У меня следующий домашний вопрос: предположим, вам даны две последовательности S1 и S2 из n элементов, возможно, содержащие дубликаты, для которых определено отношение общего порядка.Опишите эффективный алгоритм для определения, содержат ли S1 и S2 одинаковый набор элементов.Проанализируйте время выполнения этого метода

. Чтобы решить этот вопрос, я сравнил элементы двух массивов, используя retainAll и HashSet.

Set1.retainAll(new HashSet<Integer>(Set2));

Это решит проблему в постоянное время.Нужно ли сортировать два массива до шага retainAll, чтобы повысить эффективность?

Answer 1

Я подозреваю из кода, который вы опубликовали, что вы упускаете суть задания.Идея не в том, чтобы использовать библиотеку Java для проверки, равны ли две коллекции (для этого вы можете использовать collection1.equals(collections2). Скорее, дело в том, чтобы придумать алгоритм для сравнения коллекций. Java API не определяет алгоритм:это скрыто в реализации.

Без предоставления ответа позвольте мне привести пример алгоритма, который работал бы, но не обязательно эффективен:

for each element in coll1
    if element not in coll2
        return false
    remove element from coll2
return coll2 is empty

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

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