如何计算big-theta

Question

有没有人能给我一个实时的例子，告诉我如何计算大θ。

大θ是否类似于平均情况，(最小-最大)/2？

我的意思是(最小时间-大O)/2

如果我说错了，请纠正我，谢谢

Answer 1

Big-theta表示法表示以下规则：

对于任意两个函数f(n)，g(n)，如果当n增长到无穷大时，f(n)/g(n)和g(n)/f(n)都有界，则f = Θ(g)和g = Θ(f)。在这种情况下，g既是f增长的上限，也是增长的下限。

下面是一个算法示例：

def find-minimum(List) 
  min = +∞
  foreach value in List 
    min = value if min > value
  return min

我们希望评估成本函数c(n)，其中n是输入列表的大小。此算法将对列表中的每一项执行一次比较，因此为c(n) = n。

当n变为无穷大时，保持有界的c(n)/n = 1，因此c(n)的增长速度不会比n快。这就是大O符号c(n) = O(n)的含义。相反，n/C(n) = 1也是有界的，所以c(n)的增长速度不会比n慢。由于它的增长既不慢也不快，所以它必须以相同的速度增长。这就是theta符号c(n) = Θ(n)的含义。

请注意，c(n)/n²也是有界的，因此c(n) = O(n²)以及- big-O符号只是复杂度的上界，因此任何O(n)函数也是O(n²)，O(n³)...

然而，由于n²/c(n) = n不是有界的，那么c(n) ≠ Θ(n²)。这是big-theta符号的有趣属性:它既是复杂度的上界，也是下界。

Answer 2

大θ是函数T(n)：if：Omega(f(n))<=T(n)<=O(f(n))的紧界，那么Theta(f(n))是T(n)的紧界。

换句话说，Theta( f (n))‘描述’一个函数T(n)，如果O big O和Omega都‘描述’相同的T，具有相同的f。

例如，具有正确中值选择的快速排序，总是最多花费O(nlogn)，至少Omega(nlogn)，因此具有良好中值选择的快速排序是Theta(nlogn)

编辑：在评论中添加了讨论：

搜索一个数组仍然是Theta(n)。Theta函数并不表示最坏/最好的情况，而是所需情况的行为。即，搜索一个数组，T(N)=最坏情况下的操作数。在这里，显然是T(n)<=O(n)，但也是T(n)>=n/2，因为在最坏的情况下，你需要迭代整个数组，所以T(n)>=Omega(n)和Theta(n)是渐近界的。

Answer 3

从http://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations中，我们了解到“大O”表示一个上界，而“大Theta”表示一个上界和下界，即在n走向无穷大时的极限中：

f(n) = O(g(n))      -->    |f(n)| < k.g(n)

f(n) = Theta(g(n))  -->    k1.g(n) < f(n) < k2.g(n)

所以你不能从Big O中推断出Big Theta。