Оптимизируя алгоритм O (n ^ 2) со словарем, можно ли go дальше

Question

Есть 2 набора:

Набор 1 значений (содержащий все возможные значения) Набор 2 значений (содержащий некоторые из возможных значений в Набор 1)

Для каждого соответствия мы В наборе 1 укажем, что мы его нашли.

Способ сортировки O (n ^ 2):

foreach(var set1Variable in set1) {
    foreach(var set2Variable in set2) {
        if(set1Variable == set2Variable )
            set1.indexOf(set1Variable).Found = true;
    }
}

Оптимизируется с помощью словаря.

Как «хорошо» или «плохо» является первым решением. Как насчет словаря? Что мы должны рассмотреть? Каков оптимальный способ разобраться в этом и почему?

Answer 1

Вы можете создать TreeSet и добавить в него все наборы.

TreeSet myTreeSet = new TreeSet();
myTreeSet.addAll(myHashSet);
System.out.println(myTreeSet);

Предполагая, что ваши наборы имеют размер n, Сложность пространства равна O (n) и Сложность времени O (nlogn)

Answer 2

• Предлагаемое решение - O(n^2) время без дополнительного пробела.
• Словарное решение (где все элементы наименьшего набора вставляются в словарь) может быть O(n) / O(nlogn) (в зависимости от того, какой словарь, дерево или ха sh) время и O(n) пространство.
• Вы также можете получить O(nlogn) время и без дополнительного пространства, отсортировав два контейнера, а затем повторив параллельно, чтобы найти соответствующие элементы.

Что лучше?

Зависит от конкретных c потребностей и ограничений. Если вы не можете позволить себе дополнительное место, словарное решение становится неосуществимым. Если O(nlogn) время слишком много, вам следует придерживаться хеширования.

---

Приложение: псевдокод решения 3 (сортировка):

sort(set1)
sort(set2)

iter1 = set1.iterator()
iter2 = set2.iterator()
while iter1.has_next() and iter2.has_next():
  if iter1.item() == iter2.item():
    set2.add(iter1.item())
    iter1.next()
    iter2.next()
  else if iter1.item() < iter2.item():
    iter1.next()
  else:
    iter2.next()