递归函数的复杂性

我有一个递归函数，我试图找出它的复杂性。表示P（n） - 函数的运行时间（当给定参数n时）。我知道：P（n）= n +（n-1）* P（n-1）[p（1）= 1]递归函数的复杂性

我怎样才能表达P（n））？

2011-12-30 Belgi

如果你想了解如何解决这种递归设备，你可以阅读这篇维基百科文章：http://en.wikipedia.org/wiki/Recurrence_relation#Solving。此外，我相信你的问题属于http://math.stackexchange.com/，因为它全部是关于解决递归关系'P（n）= n +（n-1）* P（n-1）[p 1）= 1]'并且与编程无关。 – bezmax 2011-12-30 10:51:49

它是功课吗？ – codeling 2011-12-30 10:52:53

@Max发现表达式的复杂性与计算机科学和编程有很大关系。 – SomeWittyUsername 2012-10-25 06:07:30

这将是O（n ⁿ）。注意，如果你开始扩展表达式，每次迭代你就会得到一个幂n的元素增加1。这将是主导因素，所以其他人可以因O（）计算而被放弃。有关更正式的解决方案，请参阅@Max提供的链接。

来源

2012-10-25 06:06:42 SomeWittyUsername

递归函数的复杂性

回答

相关问题