嵌套 for 循环的复杂性

Question

我正在尝试使用 Big O 表示法计算出我的算法的时间，但我找不到关于它的非常清楚的解释。

基本上，我的算法包括将新数组与“父”数组中的所有其他数组进行比较。

为此，我有一个 for 循环，它迭代父数组中的所有元素，寻找一个看起来像新创建的数组的数组。

这是代码：

bool AlreadyExistingArray(Array array)
{
    bool areEqual = true;
    foreach (Array a in arrayEntries)
    {
        if (a.count != array.count)
            continue;

        foreach (int i in array)
        {
            if (!a.contains(i))
            {
                areEqual = false;
                break;
            }
        }
        if (areEqual)
        {
            areEqual = false;
            foreach (int i in a)
            {
                if (!a.contains(i))
                {
                    areEqual = false;
                    break;
                }
            }
        }
    }
    return areEqual;
}

我知道每个 for 循环都应该是 O(n)，但是，复杂性是否应该组合？由于我正在处理不同大小的数组，因此我很确定不能将复杂性视为 O(n^2)。

希望我说清楚了！否则，让我知道，我会尝试进一步澄清。

编辑：改变算法。

Answer 1

Big-Oh 的一些背景知识：

您在这里得到这么多不同答案的原因是，Big-O 分析并不像计算程序运行的步数那么简单。这个教给计算机科学家的简化版本是 Big-O、Big-Omega 和 Big-Theta 函数渐近界概念的近似（通常就足够了）。实际上有一个Big-O的正式定义可以消除这些歧义。

尽管如此，让我们坚持下去。我从评论中得到的回答是这样的：

呼叫arrayEntries的大小：len(arrayEntries) = n和数组的大小len(array) = m和排列最大条目的大小len(largestOfarray) = k（即调用最大的变量的大小一）。那么你的算法是 O(n(m+k))。n、m 或 k 中的任何一个是永远不会改变大小的常数，只需将它们从该等式中删除即可。

让我解释一下上面的内容。Big-O的定义大致是：

在计算机科学中，大 O 符号用于根据算法对输入大小变化的响应方式对算法进行分类，例如当问题大小变得非常大时，算法的处理时间如何变化。

当你说一个算法是O(n^2)，这意味着这个。你是说你的算法的运行时间可以表示为某个函数T(n)（注意它只有一个变量 n）并且渐近T(n)增长不快于n^2（也就是说，非常粗略地说，随着 n 变得非常大，函数f(n) = n^2在 n 处的梯度将大于 T(n) 在 n) 处的梯度。

现在在前面的例子中，算法的运行时间取决于一个变量 n。这并非总是如此。想象一下你有一个这样的程序：

void algorithm(Array arrayM, Array arrayN) {
    for(int i : arrayN) {
        // runs len(arrayN) = n times
    }
    for(int j : arrayM) {
        // runs len(arrayM) = m times
    }
}

该算法的运行时间是一个取决于 arrayM 和 arrayN 大小的函数，因此将表示为T(n,m)。现在如果这些大小是自变量（即 arrayM 的大小与 arrayN 的大小无关），则该算法的运行时间为O(m+n)。但是，如果 arrayM 的大小确实取决于 arrayN 的大小（假设它是通过将 arrayN 的一半元素复制到其中来初始化的），那么len(arrayM) = m实际上取决于 n 这样m = n/2。因此，您的算法的时间复杂度以前O(m+n)是 ，现在是O(n+n/2) = O(n)。这本质上是因为您的运行时函数T(n,m)现在可以写成T(n, n/2) ~ T(n)即它是一个变量的函数。

您的具体示例：

现在，在你的程序的情况下，首先让我们假设的大小arrayEntries len(arrayEntries) = n和大小排列 len(array) = m，并在最大条目的大小排列（最大可能的一个）len(largestOfarray) = k，是完全独立的变量不依赖于对方. 这不是一个不合理的假设，因为您在其中一条评论中说“内部循环不依赖于外部循环的任何值”，因为它是用户输入的数量，并且输入的长度可能是任意长的一个用户可能会输入长度为 1 的内容，而另一个用户可能会输入 1000 个字符长的行。

由于 n、m 和 k 是独立的，因此您的复杂性是。您的外循环运行 n 次，在每次迭代中，第一个内循环将运行 m 次，第二个将在最坏情况下运行 k 次。因此，您的总复杂度为O(n(m+k))。但仅此而已吗？不完全是。

看到 n、m 和 k 有一些界限。也就是说，用户输入 (k) 的长度可能有限制（即如果它是从 stdin 中获取的，那么它可能不会超过 1000 个字符）。如果是这样，你可以合理地说最坏的 k 可能是 1000，所以我们可以把它当作一个常数，然后你的算法的复杂性是O(nm)因为常数 k 被根除。这一步完全取决于你认为你的程序将如何使用，但如果你想安全，你可以说复杂性是O(n(m+k)).

然而，这确实引出了一个问题，难道 m 和 n 也是有界的，因为它们的大小有限制（即您的操作系统将为您的程序分配多少内存），因此被视为常量？从技术上讲，是的。在一些算法分析中，这有时是一件有用的事情（例如在缓慢增长的算法的情况下）。

归根结底，这完全取决于您认为您的程序将如何工作以及做出哪些合理的假设（即 k 可以被视为常数）以及应该避免哪些假设。在我个人看来，这个算法可能是O(n(m+k))，O(nm)但我不会削减它更多；m 和 n 似乎与您的描述非常独立。

重要编辑（在您的代码编辑后上面的答案不正确）：

An interesting case study actually is what was commented to this answer below by @frenzykryger; a detail I missed out because you edited your question while I was writing the answer. The commenter said that you changed the start of your outer loop to check if the size of a is equal to the size of array. This means the number of times your second inner loop will run (i.e. the size of k as described above) now depends completely on m (recall m was the size of array), namely k = m. Thus your algorithm is O(n(m+m)) = O(nm). Now if you are guaranteed that m is always less than n, then the algorithm would be O(n^2) (the m can be discarded). But if m is unbounded (could be any size), then the algorithm remains O(nm).

Final Remarks:

As you can see, Big-Oh analysis is something that sometimes doesn't have a single right answer. It all depends on how your program will behave, what sort of inputs you are guaranteed to get, and many other factors. If all this makes you wish there were a more rigorous way to define it, there certainly is - just google "Big-Oh formal definition", read some links, head on over to mathematics stack exchange, and you'll have yourself a guaranteed party.