Ω（大
我正在读对数和算法运行时间的增长率。
但是，我有一个理解Big-Ω（Big-Omega）符号的问题。
我知道我们将它用于'渐近下界'，并且我们可以表达算法至少需要一定时间的想法。
考虑这个例子：
var a = [1,2,3,4,5,6,7,8,9,10];
有人选择一个数字。 我写了一个程序，试图用线性搜索来猜测这个数字（1,2,3,4 ......直到它猜到数字）。
我可以说算法的运行时间是其输入大小的函数，所以这些都是真实的（ n是数组中元素的数量）：
当谈到Big-Ω时，以我的理解，算法的运行时间为Ω（1），因为它是找到所选数字所需的最少量猜测（例如，如果玩家选择1（第一项在数组中））。
我认为这是因为这是我在KhanAcademy上找到的定义：
有时候，我们想说一个算法至少需要一定的时间 ，而没有提供上限。 我们使用大Ω符号; 那是希腊字母“欧米茄”。
我有权说这个算法的运行时间是Ω（1）吗？ 它是否也是Ω（n），如果是 - 为什么？
大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）是显而易见的，所以它比欧米茄（1）更好地说欧米茄（n），就像它更好地说O（n）而不是O（n ^ 2）。
链接地址: http://www.djcxy.com/p/39733.html上一篇: Ω (Big