如何计算big-theta

Question

有人可以为我提供一个如何计算大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 = 1这仍然 n是无限的,因此c(n)增长速度不快n.这就是big-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²).这是大-θ符号的有趣特性:它既是一个上限,并在复杂的下限.