algorithm - 如何计算大θ

有谁能给我提供一个计算大θ的实时例子吗？
大θ是平均情况（最小最大值）/2吗？
我是说（最短时间-大O）/2
如果我错了，请纠正我，谢谢

最佳答案

大θ表示法表示以下规则：
对于任何两个函数f(n)，g(n)，如果f(n)/g(n)和g(n)/f(n)都有界，因为n增长到无穷大，则f = Θ(g)和g = Θ(f)。在这种情况下，g既是f增长的上限，也是c(n)增长的下限。
下面是一个算法示例：

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

我们希望评估成本函数n，其中c(n) = n是输入列表的大小。此算法将对列表中的每个项执行一次比较，因此c(n)/n = 1。
n当c(n)到达无穷远处时仍保持有界，因此n的增长速度不比c(n) = O(n)快这就是big-O符号n/C(n) = 1的含义相反，c(n)也保持有界，因此n的增长速度不慢于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²)这是大θ符号的有趣性质：它既是复杂性的上界又是下界。

关于algorithm - 如何计算大θ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7453996/