大O和Omega表示法 [英] Big-O and Omega Notations

问题描述

我正在阅读此问题 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表示法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！