在分析一些代碼，我已經寫了，我來了下面迴歸方程爲它的運行時間 -階乘運行時間
T（N）= N * T（N-1）+ N！ + O（n^2）。
最初，我假定O（（N + 1）！）= O，並且因此我解決這樣的方程（N！） -
T（N）= N！ + O（n！）+ O（n^3）= O（n！）
推理甚至每次遞歸都產生了另一個n！ （而不是（n-1）！，（n-2）！等），它仍然只會達到n * n！ =（n + 1）！ = O（n！）。最後一個參數是由於平方和。但是，在考慮了一些後，我不確定我的假設O（（n + 1）！）= O（n！）是否正確，事實上，我很確定它不是正確的，噸。
如果我就在思考我做了一個錯誤的假設，我真的不知道如何真正解決上述迴歸方程，因爲對於階乘的總和沒有公式...
任何指導意見將不勝感激。
謝謝!!!
的問題：
T(n) = n*T(n-1) + n! + O(n^2)
這就是你混合兩種不同類型的條款。最後的+剩下的一切都指向一個數字;在該權利的右邊是O(n^2)，它表示漸近增長的所有函數的類別不會快於n^2。
假設你的意思是：
T(n) = n*T(n-1) + n! + n^2
然後
T(n) in O(n!)因爲
n!是在和增長最快的任期。 （其實，我不確定
n*T(n-1)是不是越來越快 - 我的combinatorics不是那麼強大）。
擴大了遞歸來看，遞歸「呼」地
n*T(n-1)減少了一些功能，這是
O((n!)!)
O(n!)等功能爲一體的
O(n!)。
完全展開遞歸術語，它將成爲增長最快的術語。有關正確擴展的各種建議，請參閱評論。
由於您正在查看運行時，我假設O(n^2)意味着該術語的操作次數。根據該假設，n!可以在O(n)時間（1*2*3*...*n）中計算。因此，與O(n^2)期限相比，它可以下降。然後在大致爲O（n^2）的O（（n-1）^ 2）時間內計算T(n-1)。把它放在一起，你有東西在運行
O(n^2) + O(n) + O(n^2)
產生一個O(n^2)算法。
O（n^2）在這裏的意思是簡單地稱爲Big-O符號，如果它使計算更容易，它可以簡單地替換爲「n^2」。但是，T（n-1）項乘以n。如果方程是T（n）= n * T（n-1），答案將是T（n）= n !.那麼，如果我在右側添加更多條款，怎麼可能是O（n^2）呢？ – Adam
@Adam - O（n^2）在Big-O表示法中不能被n^2替換。 n^2需要2次操作，而不是O（n^2）次操作。我想你可能會被Big-O的含義所困惑。 Big-O指的是完成某項任務所需的操作次數 - 它沒有說明任務的輸出是什麼。例如'n！'採取'n'操作。 – mgilson
在課堂上，我們使用Big-O符號來表示「與...在同一數量級上運行的東西」。它意味着一個緊密的漸近界。 – Adam
我想通了。（n）= n * T（n-1）+ n！（012） + O（n^2）= n * T（n-1）+ n！ = n *（（n-1）T（n-2）+（n-1）！）+ n！ = n（n-1）T（n-2）+ 2n！ = ... = n！ = n * n！ = O（n * n！）
您是在測量階乘算法的時間還是這是您測量其他函數的結果？ –
我編寫的函數旨在接收一個列表並輸出一個包含其所有排列的列表。它用於計算矩陣的行列式。基本上，函數遍歷列表中的每個成員（總共n個），併爲每個成員創建一個不包含該成員的子列表（O（n）），計算子列表的所有排列（T（n- 1）），然後遍歷每個這樣的排列，追加到每個被取下的數字（（n-1）！）。總而言之，我得到了我之前寫的遞歸方程。行列式計算通常採用O（n！），我也在Wikipedia上看到它的提及。 – Adam
你可以忽略'O（n^2）'這個詞，因爲'n！ = O（n^n）'由Sterling近似得出。 – chepner