理解Big-Ω(Big-Omega)表示法

Question

我正在阅读对数和算法运行时间的增长速度。

然而，我在理解Big-Ω(Big-Omega)表示法时遇到了问题.

我知道我们用它来表示“渐近下界”，并且我们可以表达一个算法至少需要一定时间的想法。

考虑一下这个例子：

var a = [1,2,3,4,5,6,7,8,9,10];

有人选择了一个数字。我写了一个程序，试图用线性搜索来猜测这个数字(1，2，3，4.直到它猜出这个数字)。

我可以说，该算法的运行时间是其输入大小的函数，因此这是正确的(n是数组中的元素数)：

1. Θ(n) (大-Theta表示法-渐近紧界)
2. O(n) (大-O表示法-上界)

对于Big-Ω，据我理解，该算法的运行时间将是Ω(1)，因为它是查找所选数字所需的最少数量的猜测(例如，如果玩家选择了1(数组中的第一项)。

我想这是因为这是我在KhanAcademy上找到的定义

有时，我们想说的是，一个算法至少要花费一定的时间，而不需要提供一个上限。我们使用大Ω表示法，这是希腊字母“omega”。

我说得对吗?这个算法的运行时间是Ω(1)吗？如果是的话，它也是Ω(n)吗?为什么？

Answer 1

大O、Theta或Omega表示法都是指当问题的大小趋于无穷大时，解是如何渐进地扩展的，然而，它们实际上应该以您正在测量的内容为前缀。

通常，当人们谈论大O(n)时，通常意味着最坏的情况复杂性是O(n)，然而，人们有时确实看到它用于典型的运行时间，特别是对于具有随机性元素或完全不能保证收敛的启发式或算法。

在这里，我们大概是在讨论最坏的情况复杂性，即Theta(n)，因为它是Theta(n)，它也是O(n)和Omega(n)。

证明未知情况下界的一种方法是说X是该算法最简单的情形，这里最好的情况是O(1)，因此我们可以说该算法至少取Omega(1)和至多O(n)，Theta是未知的，这是正确的用法，但目的是给仍然是真的Omega求出最高可能的界，对于仍为真的O(n)求出最低可能的界。这里欧米茄(N)是明显的，所以说欧米茄(N)比欧米茄(1)更好，就像说O(n)而不是O(n^2)一样。