Big O 会是一个嵌套的 for 循环,里面有一个 Any() 吗?
What would the Big O be of a nested for loop with an Any() inside it?
这个问题基本上是我 的后续问题。我真的很想说说这个算法的 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()
在结果中的哪个位置匹配...
它很接近,但是正如其他人提到的那样它将是 O(n*m)
,因为每个集合的大小不同(最好的情况是 O(n)
,最坏的情况是 O(n*m)
)否则,如果您迭代相同大小的集合两次,您将得到 O(n^2)
.
在Any()
看幕后
您可以查看 the source for the Enumerable.Any()
method 以进一步深入研究。您会看到一个 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)
.
设 A
的长度为 N
,B
的长度为 M
。我们有两个极端情况:
最差一个:
a => test.Contains(a)
returns false
在每个 a
上,所以 A.Any
必须扫描 整个 A
和我们有
O(N * M)
最好的一个:
a => test.Contains(a)
returns true
在 A
的第一项上,因此 A.Any
returns 立即 并且我们只有
O(M)
实际复杂度介于两者之间(包括两个边界):
[O(M)..O(M*N)]
.Any()
应该是 O(n)
因为它搜索容器直到找到第一个匹配的实例。因此,在 foreach 循环中应该是 O(n^2)
.
它本质上是一个嵌套的for循环,所以最坏情况下的大O应该是O(n^2)
我假设您提供 A
和 B
只是为了举例说明它们的内容,并且您知道复杂性仅对输入集(如平均、最差和最佳情况)有意义,不适用于个人输入。
我的观点是,根据问题要求和用例,您可以对代码复杂度做出非常不同的估计。
设n
为A.Length
,m
为B.Length
。然后可以通过几种不同的方式计算给定代码的复杂性:
假设 string.Contains
是 O(1)
。在实践中,可以做出这样的强假设,例如,如果我们确定没有字符串的长度超过某个预先固定的长度。那么代码复杂度当然是O(n*m)
.
假设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)
.
这个问题基本上是我
所以给定两个数组:
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()
在结果中的哪个位置匹配...
它很接近,但是正如其他人提到的那样它将是 O(n*m)
,因为每个集合的大小不同(最好的情况是 O(n)
,最坏的情况是 O(n*m)
)否则,如果您迭代相同大小的集合两次,您将得到 O(n^2)
.
在Any()
您可以查看 the source for the Enumerable.Any()
method 以进一步深入研究。您会看到一个 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)
.
设 A
的长度为 N
,B
的长度为 M
。我们有两个极端情况:
最差一个:
a => test.Contains(a)
returns
false
在每个a
上,所以A.Any
必须扫描 整个A
和我们有O(N * M)
最好的一个:
a => test.Contains(a)
returns
true
在A
的第一项上,因此A.Any
returns 立即 并且我们只有O(M)
实际复杂度介于两者之间(包括两个边界):
[O(M)..O(M*N)]
.Any()
应该是 O(n)
因为它搜索容器直到找到第一个匹配的实例。因此,在 foreach 循环中应该是 O(n^2)
.
它本质上是一个嵌套的for循环,所以最坏情况下的大O应该是O(n^2)
我假设您提供 A
和 B
只是为了举例说明它们的内容,并且您知道复杂性仅对输入集(如平均、最差和最佳情况)有意义,不适用于个人输入。
我的观点是,根据问题要求和用例,您可以对代码复杂度做出非常不同的估计。
设n
为A.Length
,m
为B.Length
。然后可以通过几种不同的方式计算给定代码的复杂性:
假设
string.Contains
是O(1)
。在实践中,可以做出这样的强假设,例如,如果我们确定没有字符串的长度超过某个预先固定的长度。那么代码复杂度当然是O(n*m)
.假设
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)
.