了解大O
给定以下代码，3. 的复杂度是多少？我如何表示具有以下复杂度的简单算法？
O(n²+n)
O(n²+2n)
O(logn) O(nlogn)
var collection = new[] {1,2,3};
var collection2 = new[] {1,2,3};
//1.
//On
foreach(var i in c1)
{
}
//2.
//On²
foreach(var i in c1)
{
foreach(var j in c1)
{
}
}
//3.
//O(nⁿ⁺ᵒ)?
foreach(var i in c1)
{
foreach(var j in c2)
{
}
}
Given the following code, what is the complexity of 3. and how would I represent simple algorithms with the following complexities?
O(n²+n)
O(n²+2n)
O(logn)
O(nlogn)
var collection = new[] {1,2,3};
var collection2 = new[] {1,2,3};
//1.
//On
foreach(var i in c1)
{
}
//2.
//On²
foreach(var i in c1)
{
foreach(var j in c1)
{
}
}
//3.
//O(nⁿ⁺ᵒ)?
foreach(var i in c1)
{
foreach(var j in c2)
{
}
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
3 是 O(n*m)，如果两个集合大小相同，则为 O(n^2)。
O(n^2+n) 是没有意义的，因为 n 小于 n^2。写成O(n^2)就可以了。
最体面的比较排序算法的运行时间为O(n*log(n))。如果你不知道的话，请查看维基百科。
二分搜索 的时间复杂度为 O(log(n))。
3 is O(n*m), or O(n^2) if the two collections are the same size.
O(n^2+n) is pointless because n is smaller than n^2. Just write O(n^2).
Most decent comparison sort algorithms run at O(n*log(n)). If you don't know any, look on Wikipedia.
A binary search is O(log(n)).
执行外部
foreachn = |c1|次（其中 |x| 是c1的大小），而内部foreach执行 m = |c2|次。总共是 O(n * m) 次。这与 O(n^2) 相同。需要 O(n^2) 时间的事情是在聚会上与其他所有人一起敬酒，假设总是有两个人在敬酒，并且一次只有一个人敬酒。
同上； O(n^2) 项占主导地位。 O(n^2) 工作量的另一个例子是在长度为 n 的方形花园中种植树木，假设种植每棵树需要恒定的时间，并且一旦种植一棵树，其他树就被排除在外从它的附近。
的一个例子是通过重复选择接下来需要搜索的页面区域的中点来在字典中查找单词。 （换句话说，二分搜索。）
使用上述算法，但现在您必须找到字典中的每个单词。
The outer
foreachis executed n = |c1| times (where |x| is the size ofc1), while the innerforeachis executed m = |c2| times. That's O(n * m) times in total.This is the same as O(n^2). Something that takes O(n^2) time would be drinking a toast with every other person at a party, assuming that there's always exactly two people in a toast, and only one person does the toasting at a time.
Same as above; the O(n^2) term dominates. Another example of an O(n^2) effort is planting trees in a square garden of length
n, assuming it takes constant time to plant each tree, and that once you plant a tree other trees are excluded from its vicinity.An example of this would be finding a word in a dictionary by repeatedly picking the midpoint of the region of pages you need to search next. (In other words, a binary search.)
Use the above algorithm, but now you have to find every word in the dictionary.
不存在 O(n²+n) 或 O(n^2 + 2n)。抛开算法复杂性的大部分数学基础不谈，您至少需要知道它是“渐近的”。当 N 接近无穷大时，n^2 + n 的值由 n ^ 2 项主导，因此这就是 n^2 + n 的渐近复杂度。
3 的复杂度为 O(I * J)，其中 I 和 J 是 c1 和 c2 中输入的大小。
There is no O(n²+n) or O(n^2 + 2n). Leaving aside most of the mathematical foundations of algorithmic complexity, you at least need to know that it is "aymptotic." As N approaches infinity, the value of n^2 + n is dominated by the n ^ 2 term, so that is the asymptotic complexity of n^2 + n.
3's complexity is O(I * J), where I and J are the size of the inputs in c1 and c2.
说实话 O(n²+n) & O(n²+2n) 是相同的。
Truth be told O(n²+n) & O(n²+2n) are the same.
3 的复杂度为 O(m*n)。
不存在复杂度 O(n2+n) 或 O(n2+2n)。它只是 O(n2)。这是因为 n 是 o(n2)。
O(log(n)) 的示例是二分查找。
O(n*log(n)) 的示例是合并排序。
Complexity of 3 is O(m*n).
There is no complexity O(n2+n) or O(n2+2n). It is just O(n2). This is because n is o(n2).
Example of O(log(n)) is binary search.
Example of O(n*log(n)) is merge sort.