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

Question

这个问题基本上是我的 answer here 的后续问题.我真的很想说说这个算法的 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

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

1. 最差:

   a => test.Contains(a) 
   

   在每个 a 上返回 false，因此 A.Any 必须扫描整个 A 我们有

   O(N * M) 
   

2. 最好的:

   a => test.Contains(a) 
   

   在 A 的第一项返回 true，因此 A.Any 立即返回，我们有只有

   O(M)
   

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

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