Big O嵌套在里面的Any（）的for循环会是什么？ [英] What would the Big O be of a nested for loop with an Any() inside it?

问题描述

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

This questions is basically a follow-on from my answer here. I really wanted to say what the Big-O of this algorithm would be, but I wasn't sure my claim was completely sound.

因此有两个数组：

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（）匹配...

I believe it to be somewhere between O(n) and O(n^2) as it depends where in the result the Any() matches...

推荐答案

让 A 的长度为 N 和 B 的长度为 M 。我们有两种极端情况：

Let length of A be N and length of B be M. We have two extremal cases:

1. 最差之一：

a => test.Contains(a) 

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

returns false on every a, so A.Any has to scan the entire A and we have

O(N * M) 

最好一个：

a => test.Contains(a) 

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

returns true on the very 1st item of A and thus A.Any returns immediately and we have only

O(M)

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

Actual complexity is somewhere in between (both borders included):

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

这篇关于Big O嵌套在里面的Any（）的for循环会是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！