ruby-on-rails - 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 做任何事情，期望强制生成所有排列。构建所有排列的数组会占用太多内存。

此方法在 n 为 10 到 13 时被调用了 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**k k 个元素的数组。

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

对于k=n，它变为O(n**n)或O(n**(n+1)) ，这甚至比 permutation 差(很多)。