嵌套的for循环总是O(n^2)吗？ [英] Are nested for loops always O(n^2)?

问题描述

我正在努力想出这段代码的复杂性(这不是一个家庭作业问题，我只是试图理解这个概念)：

public static boolean boxesHaveItem(List<Box> boxes, Item object) {
    for (Box box : boxes) {
        for (Item item : box.getItems()) {
            if (item.equals(object)) {
                return true;
            }
        }
    }
    return false;
}

因为有嵌套的for循环，所以Instt应该是O(n^2)，但这没有意义，因为框中的项数与我传递给此方法的框数无关。

可能是O(MN)，其中m=箱子中的平均物品数，n=箱子的数目？

我认为O(N)最好，其中n是传递给函数的所有框中项目的总数，但这有点奇怪，因为它们不是直接传递给函数的。

推荐答案

您在此有多个选择。在谈论复杂性时，您应该选择对受众有用的依赖项。

该方法明显取决于项的数量，它产生Theta(|items|)。因此，如果n是项目数，则Theta(n)是绝对正确的。

---

如果项与框之间存在依赖关系，例如，一个框最多可以包含5个项，则您还可以根据框的数量来表示复杂性。然后，它显然也会产生Theta(|boxes|)。

如果没有依赖关系，则不能用框数表示复杂性，因为不依赖于它。

只需选择您认为最适合您的受众的内容。

---

"嵌套的for循环总是O(n^2)吗？"

对于你的另一个问题，答案是否定的。它们并不总是O(n^2)。您可以很容易地创建这样一种情况，其中一个循环影响另一个循环的迭代，从而产生不同的复杂性。

一个小的构造示例：

for (int i = 0; i < n; i++) {
    for (int j = i; j < i + 5 && j < amount; j++) {
        ...
    }
}

该循环乍一看可能类似O(n^2)，但内部循环最多为外部循环的每个迭代创建5次迭代。因此，我们总共只收到5 * n次迭代，而不是像n^2这样的迭代。因此，复杂性为O(n)。

这篇关于嵌套的for循环总是O(n^2)吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！