T（n）（复原关系），Big O和Big Theta之间有什么区别？
我想知道这个我的算法类。 似乎不清楚BigO，Big Theta和复发关系（T（n））之间的区别是什么。例如：T（n）= 4T（n / 3）+ O（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（nlog3 4）。 由此，我们的意思是由T（n）隐含描述的函数大约以函数nlog3的速率增长4.我们可以通过引入一个大O符号的正式定义来形式化这个函数。
但是，当我们说T（n）= O（nlog34）时，我们并不排除T（n）实际上是一个小得多的函数的可能性。 例如，如果T（n）= 5，T（n）= 0（nlog3 4）的确如此，尽管它没有多少说明。 如果我们做出更强烈的主张T（n）=Θ（nlog3 4），我们断言，从长远来看，T（n）以与nlog3 4相同的速率增长。
希望这可以帮助！
链接地址: http://www.djcxy.com/p/40151.html上一篇: What is the Difference between T(n) (reccurence relations), Big O and Big Theta