複雜遞歸階乘程序的

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

2010-02-24 Karan

我不知道，男人。我可以編寫一個非常糟糕的遞歸階乘程序，至少需要O（n！）個時間才能完成。如果你想分析算法，你需要實際的算法。 – Welbog 2010-02-24 15:44:00

如果你把乘法爲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記法是不適當的

來源

2010-02-24 15:48:31

你只能乘以適合你的記憶的數字。所以我不明白乘法是如何克服O（1）的。你能給我一個詳細的解釋嗎？ – tur1ng 2010-02-24 16:02:22

@ tur1ng，對於時間*和*額外空間[[輸入和輸出所需的顯而易見的空間，這將是荒謬的計數]]，你有大O行爲（儘管除非明確提及空間，否則通常意味着時間）。乘以O（1）的額外空間和'O（（log N）** 1.585）'及時（與Karatsuba）。「物理可訪問的宇宙」（因此任何實際上可以想象的機器）都是有限的這一事實與CS無關：通常分析（隱含地）假設一個「圖靈機」，其定義爲具有無限長的「磁帶」（無限存儲）。 – 2010-02-24 16:08:37

BTW @ tur1ng，你應該更熟悉圖靈機和它們無限長的磁帶（「適合你的記憶」 - pah！ - ） - 從http://en.wikipedia.org/wiki開始/ Turing_machine。 – 2010-02-24 16:09:56

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

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

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

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

來源

2010-02-24 15:48:41 Welbog

當您表達算法的複雜性時，它總是作爲輸入大小的函數。只有在您乘法的數字具有固定大小時，纔會假設乘法運算爲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!的素數因子分解，然後乘以所有素數因子。

來源

2011-06-01 02:37:59 gwilkins

+1用於解釋乘法的時間分析 – Moshe 2012-11-16 03:15:04

複雜遞歸階乘程序的

回答

相關問題