我正在阅读此问题 Big-O符号的定义. 但是我要发表评论的声誉不到50,所以我希望有人能帮助我.
I was reading this question Big-O notation's definition. But I have less than 50 reputation to comment, so I hope someone help me.
我的问题是关于这句话:
My question is about this sentence:
对于许多算法来说,没有单个函数g使得复杂度同时为O(g)和Ω(g).例如,插入排序的Big-O下限为O(n²)(表示找不到小于n²的东西),而Ω上限为Ω(n).
There are many algorithms for which there is no single function g such that the complexity is both O(g) and Ω(g). For instance, insertion sort has a Big-O lower bound of O(n²) (meaning you can't find anything smaller than n²) and an Ω upper bound of Ω(n).
对于较大的n,O(n²)是一个上限,而Ω(n)是一个下限,或者我可能被误解了? 有人可以帮我吗?
for large n the O(n²) is an upper bound and Ω(n) is a lower bound, or maybe I have misunderstood? could someone help me?
推荐答案
具有O(n²)的Big-O下界
has a Big-O lower bound of O(n²)
我真的不同意这种说法的混淆方式(因为big-O本身是一个上限),但是我在这里读到的是以下内容:
I don't really agree with the confusing way this was phrased (since big-O is itself an upper bound), but what I'm reading here is the following:
Big-O是一个上限.
Big-O is an upper bound.
也就是说,如果|f(n)| <= k|g(n)|作为n趋于无穷大,则f(n) ϵ O(g(n))为真(根据定义).
That is to say, f(n) ϵ O(g(n)) is true if |f(n)| <= k|g(n)| as n tends to infinity (by definition).
因此,我们有一个函数f(n) = n2(如果忽略常量因子,则为插入排序的最坏情况).我们可以说n2 ϵ O(n2),但是我们也可以说n2 ϵ O(n3)或n2 ϵ O(n4)或n2 ϵ O(n5)或....
So let's say we have a function f(n) = n2 (which is, if we ignore constant factors, the worst-case for insertion sort). We can say n2 ϵ O(n2), but we can also say n2 ϵ O(n3) or n2 ϵ O(n4) or n2 ϵ O(n5) or ....
所以我们可以找到的最小的g(n)是n2.
So the smallest g(n) we can find is n2.
但是,从总体上来说,您链接的答案是错误的-插入排序本身没有上限或下限,但具有最佳,平均和最坏的情况,具有上限和下限.
But the answer you linked to is, as a whole, incorrect - insertion sort itself does not have upper or lower bounds, but rather it has best, average and worst cases, which have upper and lower bounds.
查看我在此处发布的答案.
See the answer I posted there.
更多推荐
大O和Omega表示法
发布评论