是什么下限和紧约束之间的区别？

StackOverflow https://stackoverflow.com/questions/464078

  •  19-08-2019
  •  | 
  •  

题

使用此回答，什么是西塔（紧结合的）？

欧米茄下界，相当理解，最小时间的算法可以采取。我们知道大O是上界，指的算法可能需要的最长时间。但我有一个关于西塔不知道。

有帮助吗？

解决方案

大O 是上界，而欧米茄是下限。 西塔需要大O和Omega二者，所以这就是为什么它被称为紧结合（它必须是上部和下限）。

例如，一种算法采取Omega(n log n)至少需要n log n时间，但没有上限。一个算法以Theta(n log n)远远优先，因为它需要的至少 n log n（欧米茄Ñlog n）的和不超过 n log n（大O N日志N）。

其他提示

Θ-符号（希塔符号）被称为紧密结合的，因为它比 O形符号和Ω-符号（欧米加更精确符号）。

如果我是懒，我可以说，一个排序后的数组上二进制搜索是O（n 2 ），O（N 3 ），和O（2 < SUP>名词），以及我将在每种情况下技术上正确。这是因为O型符号只能指定一个的上限的，和二进制搜索界偏高所有的这些功能，只是不是很密切。这些懒惰估计将是无用

Θ表示法通过解决了这个问题的结合 O形符号和Ω-符号。如果我说，二进制搜索是Θ（log n）的，那让你更准确的信息。它会告诉你，该算法为界的两个的由给定函数两侧，所以它永远不会是显著比规定快或慢。

如果你有一些是 O（F（N））这意味着有是ķ， G（N）使得 F（N）≤千克（n）的

如果你有一些是Ω（F（N））这意味着有是ķ， G（N）使得 F（N）≥千克（n）的

如果你有一个的 O（F（N））的和的Ω（F（n））的一个东西的，那么它的< EM>Θ（F（N）

在维基百科文章是体面，如果有点致密的。

<强>渐近上限表示一个给定的算法的最大时间量期间执行，这取决于输入的数量。

让我们来排序算法，例如，如果数组中的所有元素是降序排列，然后对它们进行排序，将采取O(n)的运行时间，表示上限的复杂性。如果数组已经排序，该值将O(1)。

通常，O-notation用于上界的复杂度。

<强>渐近紧结合（C <子> 1 G（N）≤F（N）≤ç<子> 2 G（N））示出了平均复杂度界限为函数，具有结合的极限之间的值（上限和下限），其中c <子> 1 和c <子> 2 是常数。

短语最小时间和最大时间都有点误导这里。当我们谈论大O字符号，它不是实际的时间，我们感兴趣的是，这是当我们的输入尺寸变大的时候怎么增加。而这通常是我们所谈论的，不是平均或最坏情况下的时间的最好的情况下的，这通常不是解决我们的问题有意义。

使用在接受的答案的其它问题，例如在阵列搜索。它需要找到一个大小为列表中的特定数量的时间是N / 2 *平均some_constant。如果你把它当作一个功能f(n) = n/2*some_constant，查理给出它增加不会高于g(n) = n，在这个意义上。此外，它增加不超过g(n)慢无论是。因此，g(n)实际上既是一个上限和一个下限在大O符号f(n)的，所以线性搜索的复杂性是准确 <强>名词下，这意味着它是西塔（N）。

在这方面，在所接受的答案的其他问题的解释是不完全正确，其声称，O（n）是上限，因为该算法可在恒定的时间为一些输入运行（这是最好的情况下的我上面提到的，这是不是真的是我们想了解的运行时间）。

  

如果我是懒，我可以说，一个排序后的数组上二进制搜索是   O（N2），O（N）和O（2N），我会在每一个技术上是正确的   情况下。

我们可以使用邻 - 符号（“小-OH”）来表示的上限不是渐近紧。这两个大哦和小哦是相似的。但是，大的 - OH很可能用于定义渐近紧上限。

正下界或$ \欧米加$ bfon F（n）表示的一组功能，这些功能渐近小于或等于f（n）的即ù      G（N）≤CF（N）$ \所有$`un≥N” 对于一些C，N” $ \在$ $ \ BBB {N} $

和上界或$ \ mathit {ö} $上F（N）是指一组其是assymptotically大于或等于F（N），其数学地告诉，

的功能

$ G（N）\ GE CF（n）的\对于所有的n \ GE N '$，对于一些C，N' $ \在$ $ \ BBB {N} $

现在的$ \西塔$是的交点以上书面2

  

$\theta $

一样，如果一个算法是像 “正是$ \欧米茄\左（F（N）\右$”，那么最好还是说这是$ \西塔\左（F（N）\右）$。

或者，我们也可以说，它给我们的实际速度，其中$ \omega $为我们提供了最低的限度。

的基本区别
  

块引用

渐近上限和渐近紧 Asym.upperbound意味着给定algorythm可以与取决于输入数的时间最大量执行，用于例如在排序算法中，如果所有的阵列（n）的元素以降序然后上升他们将需要的运行时间为O（n）示出了上界的复杂性，但如果它们已经排序然后它会采取欧姆（1）所以我们通常使用的“O”表示法为上限的复杂度。

ASYM。 tightbound结合示出了用于例如（C1G（N）<= F（N）<= C2G（N））示出了紧约束限制，使得该函数具有在之间的值的两个结合的（上限及下限），得到平均情况。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top