Big O 会是一个嵌套的 for 循环，里面有一个 Any() 吗？

Question

这个问题基本上是我的后续问题。我真的很想说说这个算法的 Big-O 是什么，但我不确定我的说法是否完全正确。

所以给定两个数组：

B = [ "Hello World!", "Hello Stack Overflow!", "Foo Bar!", "Food is nice...", "Hej" ]
A = [ "World", "Foo" ]

大O是什么：

List<string> results = new List<string>();
foreach (string test in B)
{
   if (A.Any(a => test.Contains(a))
      results.Add(test);
}

我认为它介于 O(n) 和 O(n^2) 之间，因为它取决于 Any() 在结果中的哪个位置匹配...

Answer 1

它很接近，但是正如其他人提到的那样它将是 O(n*m)，因为每个集合的大小不同（最好的情况是 O(n)，最坏的情况是 O(n*m)）否则，如果您迭代相同大小的集合两次，您将得到 O(n^2).

在Any()

看幕后

您可以查看 the source for the Enumerable.Any() method 以进一步深入研究。您会看到一个 foreach 循环进行迭代，直到它找到谓词的匹配项，这加强了您对它的假设 O(n):

public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> 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).

Answer 2

设 A 的长度为 N，B 的长度为 M。我们有两个极端情况：

最差一个：
```
a => test.Contains(a) 
```
returns false 在每个 a 上，所以 A.Any 必须扫描整个 A 和我们有
```
O(N * M) 
```
最好的一个：
```
a => test.Contains(a) 
```
returns true 在 A 的第一项上，因此 A.Any returns 立即 并且我们只有
```
O(M)
```

实际复杂度介于两者之间（包括两个边界）：

    [O(M)..O(M*N)]

Answer 3

.Any() 应该是 O(n) 因为它搜索容器直到找到第一个匹配的实例。因此，在 foreach 循环中应该是 O(n^2).

Answer 4

它本质上是一个嵌套的for循环，所以最坏情况下的大O应该是O(n^2)

Answer 5

我假设您提供 A 和 B 只是为了举例说明它们的内容，并且您知道复杂性仅对输入集（如平均、最差和最佳情况）有意义，不适用于个人输入。

我的观点是，根据问题要求和用例，您可以对代码复杂度做出非常不同的估计。

设n为A.Length，m为B.Length。然后可以通过几种不同的方式计算给定代码的复杂性：

假设 string.Contains 是 O(1)。在实践中，可以做出这样的强假设，例如，如果我们确定没有字符串的长度超过某个预先固定的长度。那么代码复杂度当然是O(n*m).
假设string.Contains是O(x*y)，其中x和y是干草堆和针的长度。令 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).

Big O 会是一个嵌套的 for 循环，里面有一个 Any() 吗？

What would the Big O be of a nested for loop with an Any() inside it?

c#

algorithm

big-o