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

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

这个问题基本上是我 的后续问题。我真的很想说说这个算法的 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() 在结果中的哪个位置匹配...

它很接近,但是正如其他人提到的那样它将是 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).

A 的长度为 NB 的长度为 M。我们有两个极端情况:

  1. 最差一个:

    a => test.Contains(a) 
    

    returns false 在每个 a 上,所以 A.Any 必须扫描 整个 A 和我们有

    O(N * M) 
    
  2. 最好的一个:

    a => test.Contains(a) 
    

    returns trueA 的第一项上,因此 A.Any returns 立即 并且我们只有

    O(M)
    

实际复杂度介于两者之间(包括两个边界):

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

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

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

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

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

nA.LengthmB.Length。然后可以通过几种不同的方式计算给定代码的复杂性:

  1. 假设 string.ContainsO(1)。在实践中,可以做出这样的强假设,例如,如果我们确定没有字符串的长度超过某个预先固定的长度。那么代码复杂度当然是O(n*m).

  2. 假设string.ContainsO(x*y),其中xy是干草堆和针的长度。令 A 中最长的字符串长度为 k_AB 中最长的字符串长度为 k_B。那么代码复杂度就是 O(n*m*k_A*k_B)

对于第二种情况,还有另一种(更实用)的做法:

S_AA中所有字符串的长度总和,S_BB中所有字符串的长度总和。那么代码复杂度就是 O(S_A * S_B).

这是最坏的情况。但是,对于一般情况和大多数实际情况,string.ContainsO(x + y)。所以平均代码复杂度为 O(n*m*(k_A + k_B))O((S_B + k_A) * n + (S_A + k_B) * m).