这个问题基本上是我在在此处回答的后续问题。我真的很想说这个算法的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:
最差之一: 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循环会是什么?
发布评论