Big O嵌套在里面的Any（）的for循环会是什么？

本文介绍了Big O嵌套在里面的Any（）的for循环会是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这个问题基本上是我在在此处回答的后续问题。我真的很想说这个算法的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)]