同时循环，用于循环，标志和复杂度

Question

如果我有一个for循环来搜索某些内容，并且用while循环将其包围，那么即使从未运行两次while循环，它是否也为O（N ^ 2）？例如，在集合中搜索6

int location;
while (found == false AND quit == false)
    foreach data x in collection
        if x == 6
            location = 6
            found = true // exit prematurely
         end if
    end for
    quit = true // exit here after for loop
end while

此算法的复杂度是多少？

Answer 1

不，不是O(N^2)。 Big-O描述了您算法的最坏情况。考虑在这种情况下最坏的情况是什么。如果您要查找数字6是ints的集合，那么最糟糕的情况是它显然不存在。

因此，如果您的电话号码不存在，您将在foreach中遍历整个列表，然后无论如何都要结束。

因此，此代码的Big-O实际上是O（N）。

这里使用while完全是不正确的。