再帰関数の複雑さ

私は再帰関数を持っています、そして、私はその複雑さを理解しようとしています。は、P（n） - 関数のランタイム（パラメータnが与えられたとき）を示す。私はP（n）= n +（n-1）* P（n-1）[p（1）= 1]再帰関数の複雑さ

を知っています。）？

2011-12-30 Belgi

このような再帰的なequasionsを解く方法を理解したい場合は、このウィキペディアの記事http://en.wikipedia.org/wiki/Recurrence_relation#Solvingを読むことができます。また、あなたの質問はhttp://math.stackexchange.com/に属していると考えています。これは、すべての逐次関係を解くことであると考えられます。P（n）= n +（n-1）* P（n-1）[p 1）= 1] 'となり、プログラミングとは関係ありません。 – bezmax

は宿題ですか？ – codeling

@ Maxは表現の複雑さを知ることは、コンピュータサイエンスと特にプログラミングに非常に関連しています。 – SomeWittyUsername

O（n ⁿ）です。式の展開を開始すると、各反復で1のn乗の要素が得られます。これが支配的な要素になり、O（）計算のために他の要素を削除することができます。より正式な解決策としては、@ Maxによって提供されるリンクを参照してください。

出典

2012-10-25 06:06:42 SomeWittyUsername

答えて

関連する問題