Big O是一个嵌套的for循环，里面有Any（）会是什么？
这个问题基本上是我在这里回答的后续问题 。 我真的想说这个算法的Big-O是什么，但我不确定我的说法是完全合理的。
所以给出了两个数组：
B = [ "Hello World!", "Hello Stack Overflow!", "Foo Bar!", "Food is nice...", "Hej" ] A = [ "World", "Foo" ] 什么是大O：
List results = new List(); foreach (string test in B) { if (A.Any(a => test.Contains(a)) results.Add(test); }
我相信它介于O(n)和O(n^2)因为它取决于结果中Any()匹配的位置……
设A长度为N ， B长度为M 我们有两个极端情况：
-
最糟糕的一个：
a => test.Contains(a)每
a都返回false，所以A.Any必须扫描整个A，我们有O(N * M) -
最好的一个：
a => test.Contains(a)在
A第一项上返回true，因此A.Any立即返回 ，我们只有O(M)
实际复杂性介于两者之间（包括两个边界）：
[O(M)..O(M*N)]
它很接近，但是正如其他人提到的那样它将是O(n*m)因为每个集合的大小不同（最好的情况是O(n) ，最差的是O(n*m) ）否则，如果你两次迭代相同大小的集合，你得到O(n^2) 。
在Any()的场景后面看一看
您可以查看Enumerable.Any()方法的源代码，以便进一步深入研究。 你会看到一个foreach循环迭代，直到它找到一个谓词的匹配，这加强了你对O(n)假设：
public static bool Any(this IEnumerable source, Func predicate) { if (source == null) throw Error.ArgumentNull("source"); if (predicate == null) throw Error.ArgumentNull("predicate"); // Another loop to iterate through the collection until the predicate is matched foreach (TSource element in source) { if (predicate(element)) return true; } return false; }
正如你所看到的， Any()本身将是O(n)的长度，并且在现有循环内嵌套O(m)应该为整个代码提供O(n*m) 。 但是，它可能低至O(m) 。
我假设您仅提供A和B作为其内容的示例，并且您意识到复杂性仅对输入集合（例如平均，最差和最佳情况）有意义，而不是针对单个输入。
我的观点是，根据问题要求和用例，您可以对代码复杂度做出非常不同的估计。
设n是A.Length ， m是B.Length 。 然后可以通过几种不同的方式计算给定代码的复杂性：
-
假设
string.Contains是O(1)。 在实践中，可以做出如此强烈的假设，例如，如果我们确切地知道没有字符串比预先确定的长度更长。 那么代码复杂度当然是O(n*m)。 -
假设
string.Contains是O(x*y)，其中x和y是haystack和needle的长度。 设A的最长字符串的长度为k_A，而B的最长字符串的长度为k_B。 然后代码复杂度为O(n*m*k_A*k_B)
对于第二种情况，还有另一种（更实际的）方法：
令S_A为A所有字符串的长度之和， S_B为B所有字符串的长度之和。 然后代码复杂度为O(S_A * S_B) 。
这是最糟糕的情况。 但是对于普通情况，对于大多数实际情况， string.Contains是O(x + y) 。 因此，平均代码复杂度将是O(n*m*(k_A + k_B))或O((S_B + k_A) * n + (S_A + k_B) * m) 。
.Any()应该是O(n)因为它搜索容器，直到找到第一个匹配的实例。 因此，在foreach循环中应该是O(n^2) 。
它本质上是一个嵌套的for循环，所以对于最坏的情况，大O应该是O（n ^ 2）