algorithm - 作业：递归函数的大哦

Question

这是我作业中的一个问题。我不太确定如何解决这样的问题。

If T(n) = nT(n - 1) and T(1) = 3, then
a) T(n) = O(n^n)
b) T(n) = Ω(n!)
c) T(n) = O(2^(nlogn))
d) none of the above

我不需要这个问题的确切答案（因为它的作业），但我想知道告诉递归函数边界的方法。

Answer 1

试着解决它。假设n = 3。会有多少次迭代？如果n = 4呢？当您增加时，迭代次数的增长速度有多快n？

另一种看待它的方式是：在公式中，函数如何“分支”？线性函数没有分支，它们只有简单的 1:1 递归。指数函数将分支多次。对数函数分支，但降低了它们操作的数据的复杂性......等等。

Answer 2

 For n = 4:

   T(4) = 4 * T(4-1)
     T(3) = 3 * T(3-1)
       T(2) = 2 * T(2-1)
         T(1) = 3

每次调用（乘法和递归调用）的执行时间为 2 步。对于给定的示例，对于 4 次调用，您将有 8 个线性执行的步骤（您没有任何组合或对数算法，因此您的函数以 O(n) 为界。

对于可能的选择，您的答案是：

a) T(4) = O(4^4) -> 256 

b) T(4) = Ω(4!) -> 24

c) T(4) = O(2^(4log4)) ~> 5.27

d) none of the above

所以你的选择应该是d。希望它有所帮助。