Mathematica中的Permutations[]运行时

Question

它似乎运行得非常快，即使对于相对较大(大小为10)的集合也是如此。有人能告诉我他们特定算法的big-theta运行时吗？我在文档里找不到。

Answer 1

我第一次尝试回答这个问题是有严重缺陷的。由于大多数内部算法没有发布限制行为，因此我决定直接测量这一点。我测量了计算随机值列表的Permutations所需的时间，并计算了每个长度超过1000个值的平均值和标准差。由于所需时间的限制，我使用了最大长度为10的元素，而Permutations只能运行最大长度为12的列表。我在对数图上的结果：

​

​

平均值是一条黑线，一个标准差由平均值周围的填充区域表示。从长度5开始，它大致是笔直的，直到10点，可以检测到一条轻微的曲线。我怀疑它是O(n!)，但是对于小于7或8的长度，这真的无关紧要。即使是长度为10的排列，也显示出平均为0.241 +/- 0.012秒的可观表现。