2011-12-30 56 views
1

我有一個遞歸函數,我試圖找出它的複雜性。 表示P(n) - 函數的運行時間(當給定參數n時)。我知道:P(n)= n +(n-1)* P(n-1)[p(1)= 1]遞歸函數的複雜性

我怎樣才能表達P(n) )?

+0

如果你想了解如何解決這種遞歸設備,你可以閱讀這篇維基百科文章: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

+0

它是功課嗎? – codeling 2011-12-30 10:52:53

+0

@Max發現表達式的複雜性與計算機科學和編程有很大關係。 – SomeWittyUsername 2012-10-25 06:07:30

回答

1

這將是O(n n)。注意,如果你開始擴展表達式,每次迭代你就會得到一個冪n的元素增加1。這將是主導因素,所以其他人可以因O()計算而被放棄。有關更正式的解決方案,請參閱@Max提供的鏈接。