All*_*ang 2 algorithm recursion
这是我作业的一个问题.我不太清楚如何解决这样的问题.
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
我不需要这个问题的确切答案(因为它的功课),但我想知道告诉递归函数的界限的方法.
试试吧.假设n = 3.会有多少次迭代？如果n = 4呢？增加时迭代次数会增加多快n？
另一种看待它的方法是:在公式中,函数如何"分支"？线性函数不分支,它们只有简单的1:1递归.指数函数将分支多次.对数函数分支,但降低了它们运行的数据的复杂性......等.