Mathematica中的排列[]運行時間

即使對於較大（大小爲10）的集合，它似乎運行得非常快。任何人都可以告訴我他們特定算法的big-theta運行時間嗎？我無法在文檔中找到它。Mathematica中的排列[]運行時間

2011-07-12 JeremyKun

您能否提供一個WRI將文檔中的任何Mathematica算法的大O，Omega，Theta運行時間放在哪裏的示例？ – Simon

不，但是對於一些函數，他們確實解釋了底層實現（這個函數調用了一個使用哈希映射等的C庫...） – JeremyKun

考慮到生成的集合的數量，這可能比O（n！？或者你對它比O（n！）慢多少感興趣？（它需要進行額外的比較，因爲它不會像'{1,2,3}'那樣爲'{1,2,2}'返回相同的值）。 – Szabolcs

我第一次嘗試回答這個問題是非常有缺陷的。由於大多數內部算法沒有公佈的限制行爲，因此我決定直接測量它。我測量了計算隨機值列表的Permutations所花費的時間，並計算了每個長度的1000個值的平均值和標準偏差。我用10元，由於所需時間的最大長度，並且Permutations只能最多可列出長12.我對數圖的結果：

log plot of permutation timings up to length 10

平均值是黑線，和一個標準偏差由均值周圍的填充區域表示。從5開始，它大致直到10，在那裏可以檢測到輕微的曲線。我懷疑它是O（n！），但對於低於7或8的長度，它真的沒關係。即使長度爲10的排列也給出了可觀的顯示，平均值爲0.241 +/- 0.012s。

來源

2011-07-12 13:13:38 rcollyer

而不是以對數比例繪製'n！'所以我們可以看到它比這慢了多少？ – Szabolcs

我剛剛注意到*兩個軸都是對數的。你只打算使用日誌垂直軸，對吧？否則指數將向上曲線。 – Szabolcs

假設一個'n！'的複雜性，這應該爲所有'k'提供可比較的時間，這對於k> = 5來說是這樣。所以複雜性實際上接近於'n！'。它爲'k <5'提供更大的時間，但這可能是由於其他影響。 '表[[k， ]第一@計時[做[置換範圍[k]，{10 *（10！/ k！）}];]}，{k，5， 10}]' – Szabolcs

Mathematica中的排列[]運行時間

回答

相關問題