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

让长ABE N和长度B是M.我们有两个极端情况:

1. 在最糟糕的一个:

   a => test.Contains(a) 
   

   返回false每一个a,所以A.Any必须扫描整个 A和我们有

   O(N * M) 
   

2. 在最好的一个:

   a => test.Contains(a) 
   

   返回true第1项,A因此A.Any 立即返回,我们只有

   O(M)
   

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

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

Answer 2

这是接近,但是正如其他提到这将是O(n*m)为每个集合的大小不同(最好的情况是O(n)最差的存在O(n*m)),否则,如果你两次迭代同样大小的收集,你会得到O(n^2).

在幕后看看幕后 Any()

你可以看一下方法的来源,Enumerable.Any()进一步深入研究.你会看到一个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 3

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

Answer 4

我假设你提供A和B刚例如它们的内容,你是知道的复杂性已经为组输入才有意义(如一般的,最差和最好的情况下),而不是单独的输入.

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

我们n是A.Length和m是B.Length.然后可以通过几种不同的方式计算给定代码的复杂性:

1. 假设string.Contains是O(1).在实践中,可以做出如此强烈的假设,例如,如果我们确切地知道没有字符串比预先确定的长度更长.然后代码复杂性当然是O(n*m).

2. 假设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).