algorithm - 如何计算大θ

Question

有人可以为我提供一个如何计算大 theta 的实时示例。

大 theta 是否类似于平均情况（最小-最大）/2？

我的意思是（最短时间 - 大 O）/2

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

Answer 1

Big-theta 符号表示以下规则：

对于任何两个函数f(n), g(n), 如果f(n)/g(n)和g(n)/f(n)都随着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.

c(n)/n = 1n随着趋于无穷，它仍然有界 ，因此c(n)增长速度不超过n. 这就是 big-O notation 的含义c(n) = O(n)。相反，n/C(n) = 1也保持有界，因此c(n)增长速度不低于n. 由于它的增长既不慢也不快，它必须以相同的速度增长。这就是 theta 表示法的含义c(n) = Θ(n)。

请注意，c(n)/n²它也是有界的——big c(n) = O(n²)-O 表示法只是复杂度的上限，所以任何O(n)函数也是 O(n²), O(n³)...

然而，既然n²/c(n) = n是无界的，那么c(n) ≠ Θ(n²)。这是 big-theta 符号的有趣特性：它既是复杂度的上限又是下限。

Answer 2

Big theta 是一个紧界，对于函数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，我们了解到“Big O”表示上限，而“Big 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。