嵌套循环的复杂性 [英] Complexity of Nested for Loops

问题描述

我正在尝试使用Big O表示法来计算算法的时间，但我找不到很清楚的解释。

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

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

这是代码：

  bool AlreadyExistingArray（Array array）
 {
 bool areEqual = true; 
 foreach（arrayEntries中的数组a）
 {
如果（a.count！= array.count）
继续； 
 
 foreach（int i in array）
 {
 if（！a.contains（i））
 {
 areEqual = false; 
休息时间； 
} 
} 
 if（areEqual）
 {
 areEqual = false; 
 foreach（int in a in）
 {
 if（！a.contains（i））
 {
 areEqual = false; 
休息时间； 
} 
} 
} 
} 
 return areEqual; 
} 
  

我知道每个for循环都应该是O（n），但是，复杂度应该组成吗？由于我要处理不同大小的数组，因此我非常确定不能将复杂度视为O（n ^ 2）。

希望我已经清楚了！否则，请让我知道，我将尝试进一步澄清。

编辑：已更改算法。

解决方案

Big-Oh的小背景：

您在这里获得如此众多答案的原因是Big-O分析是不像计算程序运行的步数那样简单。向计算机科学家教授的简化版本是函数Big-O，Big-Omega和Big-Theta渐近边界的近似（通常是足够的）。实际上，Big-O有一个形式定义，可以消除这些歧义。

b
$ b

不过，让我们坚持下去。我从评论中得到的答案是这样的：

调用arrayEntries的大小： len（arrayEntries）= n 和数组 len（array）= m 的大小以及数组 len（largestOfarray）= k的最大条目的大小（即您称为 a 的最大变量的大小）。那么您的算法为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）的梯度。

  void algorithm（Array arrayM，Array arrayN）{
 for（int i ：arrayN）{
 //运行len（arrayN）= n次
} 
 for（int j：arrayM）{
 //运行len（arrayM）= m次
} 
} 
  

此算法的运行时间取决于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 和 array len（array）= m 以及 array 中最大条目的大小（可能最大的 a ） 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的大小受到限制（即有多少内存）而不能说m和n也有界您的操作系统将分配给您的程序），因此被视为常量？从技术上讲，是的。并且在某些算法分析中，有时这是一件有用的事情（例如，在算法缓慢增长的情况下）。

最终，这完全取决于您认为程序的工作方式以及要做出的合理假设（即k可以视为常数）以及应避免的假设。我个人认为，该算法为 O（n（m + k）），可能为 O（nm）但我不会再削减它了； m和n似乎与您的描述完全无关。

重要编辑（代码编辑后，以上答案不正确）：

一个有趣的案例研究实际上是@frenzykryger在下面对这个答案的评论是什么；我错过了一个细节，因为您在我写答案时编辑了问题。该评论者说，您已更改外循环的开始，以检查 a 的大小是否等于 array 的大小。这意味着您的第二个内部循环运行的次数（即如上所述的k的大小）现在完全取决于m（回想m是数组的大小），即k = m。因此，您的算法为 O（n（m + m））= O（nm）。现在，如果可以保证m始终小于n，则算法将为 O（n ^ 2）（可以丢弃m）。但是，如果m是无界的（可以是任意大小），则算法仍为 O（nm）。

Final备注：

您可以看到，Big-Oh分析有时没有一个正确的答案。这完全取决于程序的行为方式，保证获得哪种输入以及许多其他因素。如果所有这些都使您希望有一个更严格的定义方式，那么肯定有-只是谷歌 Big-Oh正式定义，阅读一些链接，继续进行数学堆栈交换，您将有自己的保证派对。

I'm trying to figure out the time of my algorithm, using Big O notation, and I couldn't find a quite clear explanation about it.

Basically, my algorithm consists in comparing a new array to all other arrays in a "parent" array.

For that, I have a for loop, that iterates all elements in the parent array, looking for an array that looks like the newly created array.

Here's the code:

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;
}

I understand that each of the for loops should be a O(n), however, should the complexity be composed? Since I'm dealing with different sized arrays, I'm quite sure the complexity cannot be considered O(n^2).

Hope I made myself clear! Otherwise, let me know and I'll try and clarify even further.

Edit: changed algorithm.

解决方案

A Little Background on Big-Oh:

The reason you are getting so many varying answers here is that Big-O analysis is not as simple as just counting the number of steps the program runs. This simplified version which is taught to Computer Scientists is an approximation (that is usually sufficient) of the concept of Big-O, Big-Omega, and Big-Theta asymptotic bounds of functions. There is actually a formal definition of Big-O which would eradicate these ambiguities.

Nevertheless, let us persist. My answer from the comments was such:

Call the size of arrayEntries: len(arrayEntries) = n and the size of array len(array) = m and the size of the largest entry in array len(largestOfarray) = k (that is the size of the largest variable you call a). Then your algorithm is O(n(m+k)). Whichever one of n,m, or k are constants that will never change size, just remove them from that equation.

Let me explain the above. The definition of Big-O is roughly:

In computer science, big O notation is used to classify algorithms by how they respond to changes in input size, such as how the processing time of an algorithm changes as the problem size becomes extremely large.

When you say an algorithm is O(n^2), what this means is this. You are saying that the runtime of your algorithm can be denoted as some function T(n) (note it only has one variable n) and asymptotically T(n) grown no faster than n^2 (that is, very roughly, as n gets very large, the gradient of the function f(n) = n^2 at n will be bigger than the gradient of T(n) at n).

Now in the previous example, the runtime of the algorithm depended on one variable n. This is not always the case. Imagine you have a program like this:

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

The runtime of this algorithm is a function that depends on the size of arrayM and arrayN so it would be denoted T(n,m). Now if these sizes are independent variables (i.e. the size of arrayM has no relation to the size of arrayN), then the runtime of this algorithm is O(m+n). However, if the size of arrayM did depend on the size of arrayN (say it was initialized by copying half the elements of arrayN into it), then len(arrayM) = m actually depends on n such m = n/2. Thus your algorithm's time complexity which was previously O(m+n), is now O(n+n/2) = O(n). This is intrinsically because your runtime function T(n,m) can now be written as T(n, n/2) ~ T(n) i.e. it is a function of one variable.

Your Specific Example:

Now in the case of your program, initially let us assume that the size of arrayEntries len(arrayEntries) = n and the size of array len(array) = m and the size of the largest entry in array (the largest possible a) len(largestOfarray) = k, are completely independent variables that don't depend on each other. This is not an unreasonable assumption since you said in one of your comments that "the inner loops do not depend on any value of the outter one" since it is number of user inputs and the length of the input might be arbitrarily long as one user might input something of length 1 and another user might input a line 1000 characters long.

Since n, m, and k are independent, your complexity is thus. Your outer loop runs n times and within each iteration, the first inner loop will run m times and the second one will at worst run k times. Thus your total complexity is O(n(m+k)). But is that all? Well not quite.

See there are some bounds to n,m, and k. Namely, that the length of the user input (k) probably has a limit (i.e. if it is being taken from stdin, then it probably won't be longer than 1000 chars). If so, you could reasonably say that the worst k could be is 1000 and so we can treat it like a constant and then the complexity of your algorithm is O(nm) because the constant k is eradicated. This step depends wholly on how you think your program will be used but if you want to be safe, you could just say the complexity is O(n(m+k)).

This does however beg the question, could one not reason that m and n are also bounded because there is a limit on how large they can be (namely how much memory your operating system will allocate to your program) and thus be treated as constants? Well technically, yes. And in some algorithmic analyses, this is a useful thing to do sometimes (such as in the case of slow growing algorithms).

Ultimately it all depends on how you think your program would work and what are reasonable assumptions to make (i.e. k can be considered a constant) and which ones to avoid. In my personal opinion, this algorithm would be O(n(m+k)) and possibly O(nm) but I wouldn't cut it more than that; m and n seem pretty independent from your descriptions.

Important Edit (answer above is not correct after your code edit):

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.

这篇关于嵌套循环的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！