while 循环、for 循环、标志和复杂性

Question

如果我有一个 for 循环来搜索某些东西，并且它被一个 while 循环包围，那么它是 O(N^2) 尽管从来没有运行 while 循环两次？例如在集合中搜索 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的使用完全不正确。

while 循环、for 循环、标志和复杂性

While loop, for loop, flag and complexity

complexity-theory

big-o

loops