Ruby内置的#permutation和#repeated_permutation方法的时间复杂度是多少？

Question

我一直在想Ruby的一些内置方法的时间复杂性,特别是这两个方法.我认为我自己想出的最好的排列方法是Θ(n·n!),Ruby的内置表现更好吗？如果是这样,请帮助我了解他们的算法.

Answer 1

排列

Array#permutation返回一个带有n!数组的枚举器，因此时间复杂度至少为O(n!).

我写了这个方法：

def slow_method(n)
  (1..n).to_a.permutation.each do |p|
    p
  end
end

它不会对 做任何事情p，除了强制生成所有排列。构建所有排列的数组会使用太多内存。

对于 10 到 13 之间的 n，此方法被调用 10 次，平均时间（以秒为单位）为：

t10 = 0.618895
t11 = 6.7815425
t12 = 82.896605
t13 = 1073.015602

O(n!)看起来是一个合理的近似值：

t13/fact(13)*fact(12)/t12 #=> 0.995694114280165
t13/fact(13)*fact(11)/t11 #=> 1.0142685297667369
t13/fact(13)*fact(10)/t10 #=> 1.0103498450722133

O(n*n!)没有：

t13/(fact(13)*13)*fact(12)*12/t12 #=> 0.9191022593355369
t13/(fact(13)*13)*fact(11)*11/t11 #=> 0.8582272174949312
t13/(fact(13)*13)*fact(10)*10/t10 #=> 0.777192188517087

生成似乎是O(n!)，但是对生成的数组执行任何操作都会使整体复杂性增加O(n*n!)。

为什么不是一代O(n*n!)？这可能来自这样一个事实：当递归生成 时，剩余的排列对于和[1,2,3,4,5].permutation是相同的。[1,2][2,1]

O(n!)已经很慢了，n永远不会比 10 大很多，所以O(n*n!)也没有差多少。对于n=20、n!是2432902008176640000和n*n!是48658040163532800000。

重复排列

[1,2,...n].repeated_permutation(k)生成n**kk 个元素的数组。

复杂度应该是O(n**k)或O(k*n**k)。

对于k=n，它变成O(n**n)或O(n**(n+1))，这甚至比对于 更糟糕permutation。