algorithm - 如何计算大θ

Question

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

big theta 是否类似于平均情况，(min-max)/2？

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

如有错误请指正，谢谢

Answer 1

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

For any two functions f(n), g(n), if f(n)/g(n) and g(n)/f(n) are both bounded as n grows to infinity, then f = Θ(g) and g = Θ(f). In that case, g is both an upper bound and a lower bound on the growth of 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 = 1 在 n 趋于无穷大时保持有界，因此 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²) 也是有界的——大 O 符号只是一个大写受复杂性约束，因此任何 O(n) 函数也是 O(n²)，O(n³)...

但是，由于 n²/c(n) = n 没有界，因此 c(n) ≠ Θ(n²)。这是 big-theta 表示法的有趣属性:它既是复杂性的上限 也是 的下限。