複雜遞歸階乘程序的

Question

什麼是一個遞歸程序，找了一些n的階乘的複雜性？我的直覺是它可能是O(n)。

Answer 1

如果你把乘法爲O(1)，那麼，O(N)是正確的。但是請注意，乘以任意長度x的兩個數字是不O(1)有限硬件 - 如x趨於無窮大，需要乘的時間長（例如，如果你使用Karatsuba multiplication，這是O(x ** 1.585)）。

理論上可以做足夠龐大的數字與Schönhage-Strassen更好，但我承認我有一個沒有任何現實世界的經驗。 x，「長度」或「數字位數」（無論在什麼基礎上，對於N的大O無關緊要，當然會隨着O(log N)的增長而增長）

如果您的意思是將您的問題限制爲足夠短號碼在O(1)相乘，那麼就沒有辦法N能「趨於無窮大」，因此大O記法是不適當的

Answer 2

假設你正在談論的最幼稚的階乘算法直到永遠。

factorial (n): 
    if (n = 0) then return 1 
    otherwise return n * factorial(n-1) 

是的，算法是線性的，爲O運行（n）的時間：T他是這樣的，因爲它每次遞減值n時間執行一次，並遞減值n直到它到達0，這意味着該功能被稱爲遞歸n倍。當然，這是假定減量和乘法都是不變的操作。

當然，如果您實現階乘一些其他的方式（例如，使用遞歸除了代替乘法），您可以用更多的時間，複雜的算法結束。雖然我不會建議使用這種算法。

Answer 3

當您表達算法的複雜性時，它總是作爲輸入大小的函數。只有在您乘法的數字具有固定大小時，纔會假設乘法運算爲O(1)。例如，如果您想確定計算矩陣乘積的算法的複雜度，則可以假定矩陣的各個分量具有固定大小。那麼假設兩個單獨矩陣組件的乘法是O(1)是有效的，並且您將根據每個矩陣中的條目數來計算複雜度。

但是，如果你想找出一種算法的複雜度來計算N!你必須假設N可以任意大，所以它是無效的假定乘法是O(1)操作。

如果要將n位數與m位數相乘，那麼天真算法（您手動完成的操作）需要時間O(mn)，但算法更快。

如果你要分析的簡單算法的複雜計算N!

factorial(N) 
     f=1 
     for i = 2 to N 
      f=f*i 

     return f 

然後在for循環的第k個步驟中，您通過k乘以(k-1)!。用於表示(k-1)!的位數是O(k log k)，用於表示k的位數是O(log k)。因此，將(k-1)!和k相乘所需的時間爲O(k (log k)^2)（假設您使用天真乘法算法）。隨後的時間由算法所花費的總金額時每一步所採取的總和：

sum k = 1 to N [k (log k)^2] <= (log N)^2 * (sum k = 1 to N [k]) =
O(N^2 (log N)^2)

您可以通過使用更快的乘算法，像Schönhage-改善這一性能Strassen對於2位n位數需要時間O(n*log(n)*log(log(n)))。

提高性能的另一種方法是使用更好的算法來計算N!。我知道的最快的計算首先計算N!的素數因子分解，然後乘以所有素數因子。