Ruby 内置的#permutation 和#repeated_permutation 方法的时间复杂度是多少？
What is the time complexity of Ruby's built in #permutation and #repeated_permutation methods?
我一直在想 Ruby 的一些内置方法的时间复杂度，尤其是这两个。我认为我自己能想到的最好的排列方法是 Θ(n · n!)，Ruby 的内置性能更好吗？如果是这样，请帮助我了解他们的算法。
排列
Array#permutation returns 具有 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.
差（很多）
有一些算法可以迭代生成列表的所有排列。
怎么样？该算法按字典顺序生成 [1,2,3,4,...,n] 的所有排列。给定一个排列，算法会在 O(1) 时间内生成下一个字典排列。
这些是步骤
- 找到最大索引
k使得a[k] < a[k + 1]，如果不存在这样的索引则排列是最后一个排列
- 找到大于
k 的最大索引 l 使得 a[k] < a[l]
- 将
a[k] 的值与 a[l] 的值交换
- 反转从
a[k + 1] 到并包括最后一个元素 a[n] 的序列
复杂度是多少？
每一步都是O(1)，有O(n!)个排列，所以总的复杂度是O(n!).
我一直在想 Ruby 的一些内置方法的时间复杂度，尤其是这两个。我认为我自己能想到的最好的排列方法是 Θ(n · n!)，Ruby 的内置性能更好吗？如果是这样，请帮助我了解他们的算法。
排列
Array#permutation returns 具有 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.
有一些算法可以迭代生成列表的所有排列。
怎么样？该算法按字典顺序生成 [1,2,3,4,...,n] 的所有排列。给定一个排列，算法会在 O(1) 时间内生成下一个字典排列。
这些是步骤
- 找到最大索引
k使得a[k] < a[k + 1]，如果不存在这样的索引则排列是最后一个排列 - 找到大于
k的最大索引l使得a[k] < a[l] - 将
a[k]的值与a[l] 的值交换
- 反转从
a[k + 1]到并包括最后一个元素a[n] 的序列
复杂度是多少？
每一步都是O(1)，有O(n!)个排列，所以总的复杂度是O(n!).