T(n)（递归关系）、Big O 和 Big Theta 之间有什么区别

Question

我想知道我的算法课上的这个问题。似乎不清楚 BigO、Big Theta 和递归关系 (T(n)) 之间的区别，例如： T(n) = 4T(n/3) + O(1)

Answer 1

递归关系是递归定义函数的一种方式。例如，递推关系

T(n) = 4T(n / 3) + O(1)

表示该函数的定义是这样的：如果您想确定 T(n)，您可以计算 T(n / 3)，将其乘以 4，即 O(1) 的某个项的加法。您可以将递归关系视为描述函数如何定义的一种方式，而无需实际为其提供显式公式。

不过，一旦有了递归关系，您通常会想要找出某种方法来了解它所描述的函数类型。它描述的是线性函数吗？是二次方的东西吗？指数级的东西？

Big-O 表示法和Big-θ 表示法是描述函数的长期增长率以及根据增长率将函数分类为不同组的工具。Big-O 表示法用于给出函数的上限，而 big-θ 表示法用于给出函数的上限和下限。

例如，使用主定理，我们可以断言上面的递推满足 T(n) = O(n ^{log ₃ 4} )。我们的意思是，由 T(n) 隐式描述的函数大约以函数 n ^{log ₃ 4}的速率增长。我们可以通过引入大 O 表示法的正式定义来形式化这一点。

不过，当我们说 T(n) = O(n ^{log ₃ 4} ) 时，我们并不排除 T(n) 实际上是一个小得多的函数的可能性。例如，如果 T(n) = 5，则 T(n) = O(n ^{log ₃ 4} ) 是正确的，尽管它没有说明太多。如果我们提出更有力的主张 T(n) = θ(n ^{log ₃ 4 )，我们就断言，从长远来看，T(n) 的增长速度与 n log ₃ 4}相同。

希望这可以帮助！