T（n）=（T（n-1）+ n！）的時間複雜度是多少？

Question

設函數F是遞歸的，並且F（k）的運行時間是T（k）。

F（k）的調用F（K-1）一次，並執行其爲O運行操作（N！）

F（0）是一個基情況下，它在恆定的時間用完。

在我的真實想法， 我認爲T(n) = T(0) + (1! + 2! + ... + n!)所以 這將是T(n) <= (n! + n! + ... + n!) for n >=1。 因此是O((n+1)!)。

但我無法確定這是否足夠。 它是一個足夠的分析？有什麼方法可以測試嗎？ （這個算法不太實際，但好奇。）

Answer 1

對於階乘總和沒有一個很好的閉合形式（exact answer是混亂的）。

但是，我們可以使用歸納來證明0！ + 1！ + 2！ + ... + n！ ≤ 2n !:

• 基本情況：0！ ≤ 2＆middot; 0 !, 0！ + 1！ ≤ 2＆middot; 1 !, 0！ + 1！ + 2！ ≤ 2＆middot; 2！
• 感應：0！ + 1！ + ... + k！ +（k + 1）！ ≤ 2k！ +（k + 1）！ ≤（k + 1）k！ +（k + 1）！ = 2（k + 1）！

所以你的復發是從2n上面界定的！並從下面的n !,這意味着你可以得到的最緊密的界限是說重現解決到Θ（n！）。