如何避免时间复杂度为O(n^2)？

Question

我有以下这段代码：

for(ArticleBasketInBean basketBean : bean.getBasket()) {
    for(ArticleDTO article : dto.getArticleList()) {
        if(basketBean.getArticleReference().equals(article.getArticleReference())) {
            article.setAddedToBasket(true);
        }
    }
}

显然，上述操作的时间复杂度为O(n^2)。对于这种情况，articleReference 是唯一的。因此，bean.getBasket() 返回的列表没有重复的 articleReference，同样适用于由dto.getArticleList()返回的列表。

我想避免嵌套迭代，并且想编写更快的代码。我该怎么做？

- Tapas Bose

---

你需要一些索引结构，例如HashMap。但是嵌套循环真的是个问题吗？我们要谈论多少篇文章？ - Thilo

简单的技巧来减少迭代次数：在第一次匹配后从内部循环中“break”出来。尽管如此，时间复杂度仍为O(n^2)。 - Thilo

你可以稍微改进一下，但最坏情况下它总是O(n^2)。 - Maroun

@fge 他还可以同时使用 HashSet 和 List。第一个是通过使用哈希码（即键）获取特定实例，第二个用于迭代目的。 - JeanValjean

@MarounMaroun 问题在于选择正确的数据结构。将 articleList 替换为 HashMap，问题迎刃而解！O(n) - SJuan76

Answer 1

使用java.util.HashSet来缓存其中一个引用集，当然前提是这些集合不是太大。通过良好的哈希函数，可以将时间复杂度降至O(n)。

- Arthur Dent

Answer 2

如果您没有太多的文章/篮子，并且正如您所说，参考文献是唯一的，那么您可以像这样做; 让我们称R为引用类型，A为文章类型，B为篮子类型：

// since all references are unique we can use that, but see below
Map<R, A> mappedArticles = new IdentityHashMap<>();

// inject articles based on references in the map, then

A article;

for (B basket: bean.getBasket())
    article = mappedArticles.get(basket.getArticleReferences());
    if (article != null)
        article.setAddedToBasket(true);

// Full list of articles is in the map's .values()

注:

• 请注意使用身份哈希集; 你可能需要为引用实现equals/hashcode（或者你使用的类型可能已经为你实现了它们）;
• 你的映射可能会随着文章的“流动”而填充，在这种情况下，你只需创建一次（如果是这样，请使其线程安全！）。

- fge

---

感谢您的答案。我已经为文章编写了hashcode和equals。 我有两个问题，我知道IdentityHashMap使用==运算符来比较对象，在HashMap的情况下是equals。使用IdentityHashMap而不是HashMap可以获得额外的性能奖励是什么？我以前没有使用过IdentityHashMap，所以我需要覆盖equals方法吗，如下所示：that.getArticleReference() == this.getArticleReference()或者 this.getArticleReference().equals(that.getArticleReference())？ - Tapas Bose

如果您已经有了hashCode和equals，那么就不需要使用IdentityHashMap；它们只是用于引用相等性的参考。 ;) - fge

Answer 3

一个简单的 break 会救你于水深火热之中。

    for(ArticleBasketInBean basketBean : bean.getBasket()) {
    for(ArticleDTO article : dto.getArticleList()) {
        if(basketBean.getArticleReference().
                                  equals(article.getArticleReference())) {
            article.setAddedToBasket(true);
            break;
        }
    }
}

- Suresh Atta

---

只是让它稍微快一点，不改变顺序。 - SJuan76

Answer 4

这就是哈希表数据结构发挥作用的地方。它并不是什么高深的东西，简单来说：

一个带有键值对的对象

复杂度将从O(n2)降至O(n)，这更好。

- UMAIR JAN YETOO