递归置换算法的复杂度
Complexity of recursive permutation algorithm
我正在阅读 Richard Bird 的算法设计Haskell，在第 2.2 节中，他考虑使用以下算法来计算列表的排列列表：
perms = foldr (concatMap · inserts) [[]]
inserts x [] = [[x]]
inserts x (y : ys)=(x : y : ys):map (y:) (inserts x ys)
然后他得出T(perms 运行时间)的递推关系为
T(n+1) = T(n) +n!(I(n) +Θ(n^2))
有理由
The function I(n) is the time to compute the list of insertions of a new element in
a permutation of length n. There are n+1 results, each of which is a list of length
n+1, and it takes Θ(n^2) to concatenate them. Finally, there are n! permutations of
a list of length n, so the insertions are computed n! times.
我的问题是为什么会出现Θ(n^2)这个词？
我试着按照书上的方法，使用显式递归展开定义
perms []=[[]]
perms (x:xs)=concatMap.inserts x foldr (concatMap.inserts) [[]] xs
所以，我们有T(n)（在递归中找到由foldr项表示的尾部排列所需的时间），现在使用I(n)和上面的定义，它是将 inserts x 映射到 foldr (concatMap.inserts) [[]] xs 的单个元素上的成本，它生成一个 n+1 列表的列表（有 n+1 个可能的插入索引）每个列表包含 n+1 元素（长度 n 与一个元素的排列），我不明白的是需要连接那些 n+1 列表，因为连接操作是在 map 的结果上完成的整体，没有映射到每个 inserts x 输出，也就是说我们有
concat.map (inserts x) [L_1,L_2,...,L_(n!)],
其中每个 L_i 有 length n 并代表 n 个元素的排列。
=concat [ inserts x L_1,inserts L_2,....]
=concat [ LL_1,LL_2,...,LL_(n!)]
其中每个 LL_i 是 n+1 个列表 [P_(i,1),P_(i,2)...,P(i,n+1)] 的列表，每个 P_(i,j) 具有 n+1 个元素。
因此串联应用于列表
[ LL_1,LL_2,...,LL_(n!)]=[P_(1,1),P_(1,2)...,P(1,n+1),P_(2,1),P_(2,2)...,P_(n!,n+1)]
这本书之前计算 concat xss 的复杂度为 Θ(mn) 和 m=length xss 由列表组成，每个列表都有 length n，我的分析给出了递推关系
T(n+1)=T(n) + n!*I(n) + Θ(n!*(n+1))，这是正确的吗？
编辑
说得更清楚一点，从递归定义来看，
T(n) 是计算长度 n 的排列的成本。I(n) 是执行单个 inserts x 操作的成本，乘以执行的次数，得到 n!*I(n)Θ(n!*(n+1))是concat的复杂度。
这取决于Haskell中的列表操作。正如您在 this document 中所见，例如，当您连接到数组时，连接成本至少是复制最小长度数组的元素。因此，如果有效地实现串联，至少在 n 个大小为 n+1 的列表的每个串联中，我们有 n 个副本的成本。因此，连接长度为 n 的 n+1 列表的时间复杂度为 Theta(n^2).
在我看来伯德犯了一个错误，而你是对的。是的，每一个 n！插入创建了一个包含 n+1 个结果的列表，每个结果都是一个包含 n+1 个元素的列表，但是 Bird 的描述似乎清楚地表明，对于每个结果，他都在想象 n+1 个 n+1 个列表的串联1 个元素到单个元素列表中，每个元素都需要 O(n^2) 时间！结果，当它只是n的外层列表！必须连接成长度 n!*(n+1)=(n+1)! 的 n+1 个列表的列表列表 个元素的列表。
具体来说，在计算[1,2,3]的排列时，需要T(2)来计算：
[[2,3],[3,2]]
并且 2 需要 I(3) 每个！插入结果：
[[1,2,3],[2,1,3],[2,3,1]]
[[1,3,2],[3,1,2],[3,2,1]]
但是，连接这些不需要对每个插入结果进行 O(3^2) 操作；它只需要连接 2！插入结果本身，每个长度为 3，之前建立为 O(2!*3) 或简单的 O(3!) 操作。
所以，你是对的，它应该是：
T(n+1) = T(n) + n!I(n) + O((n+1)!)
这没有出现在 list of errata 中，因此也许您应该向该页面上列出的地址发送电子邮件，看看他是否同意。
我正在阅读 Richard Bird 的算法设计Haskell，在第 2.2 节中，他考虑使用以下算法来计算列表的排列列表：
perms = foldr (concatMap · inserts) [[]]
inserts x [] = [[x]]
inserts x (y : ys)=(x : y : ys):map (y:) (inserts x ys)
然后他得出T(perms 运行时间)的递推关系为
T(n+1) = T(n) +n!(I(n) +Θ(n^2))
有理由
The function I(n) is the time to compute the list of insertions of a new element in a permutation of length n. There are n+1 results, each of which is a list of length n+1, and it takes Θ(n^2) to concatenate them. Finally, there are n! permutations of a list of length n, so the insertions are computed n! times.
我的问题是为什么会出现Θ(n^2)这个词？
我试着按照书上的方法，使用显式递归展开定义
perms []=[[]]
perms (x:xs)=concatMap.inserts x foldr (concatMap.inserts) [[]] xs
所以，我们有T(n)（在递归中找到由foldr项表示的尾部排列所需的时间），现在使用I(n)和上面的定义，它是将 inserts x 映射到 foldr (concatMap.inserts) [[]] xs 的单个元素上的成本，它生成一个 n+1 列表的列表（有 n+1 个可能的插入索引）每个列表包含 n+1 元素（长度 n 与一个元素的排列），我不明白的是需要连接那些 n+1 列表，因为连接操作是在 map 的结果上完成的整体，没有映射到每个 inserts x 输出，也就是说我们有
concat.map (inserts x) [L_1,L_2,...,L_(n!)],
其中每个 L_i 有 length n 并代表 n 个元素的排列。
=concat [ inserts x L_1,inserts L_2,....]
=concat [ LL_1,LL_2,...,LL_(n!)]
其中每个 LL_i 是 n+1 个列表 [P_(i,1),P_(i,2)...,P(i,n+1)] 的列表，每个 P_(i,j) 具有 n+1 个元素。
因此串联应用于列表
[ LL_1,LL_2,...,LL_(n!)]=[P_(1,1),P_(1,2)...,P(1,n+1),P_(2,1),P_(2,2)...,P_(n!,n+1)]
这本书之前计算 concat xss 的复杂度为 Θ(mn) 和 m=length xss 由列表组成，每个列表都有 length n，我的分析给出了递推关系
T(n+1)=T(n) + n!*I(n) + Θ(n!*(n+1))，这是正确的吗？
编辑
说得更清楚一点，从递归定义来看，
T(n)是计算长度 n 的排列的成本。I(n)是执行单个inserts x操作的成本，乘以执行的次数，得到n!*I(n)Θ(n!*(n+1))是concat的复杂度。
这取决于Haskell中的列表操作。正如您在 this document 中所见，例如，当您连接到数组时，连接成本至少是复制最小长度数组的元素。因此，如果有效地实现串联，至少在 n 个大小为 n+1 的列表的每个串联中，我们有 n 个副本的成本。因此，连接长度为 n 的 n+1 列表的时间复杂度为 Theta(n^2).
在我看来伯德犯了一个错误，而你是对的。是的，每一个 n！插入创建了一个包含 n+1 个结果的列表，每个结果都是一个包含 n+1 个元素的列表，但是 Bird 的描述似乎清楚地表明，对于每个结果，他都在想象 n+1 个 n+1 个列表的串联1 个元素到单个元素列表中，每个元素都需要 O(n^2) 时间！结果，当它只是n的外层列表！必须连接成长度 n!*(n+1)=(n+1)! 的 n+1 个列表的列表列表 个元素的列表。
具体来说，在计算[1,2,3]的排列时，需要T(2)来计算：
[[2,3],[3,2]]
并且 2 需要 I(3) 每个！插入结果：
[[1,2,3],[2,1,3],[2,3,1]]
[[1,3,2],[3,1,2],[3,2,1]]
但是，连接这些不需要对每个插入结果进行 O(3^2) 操作；它只需要连接 2！插入结果本身，每个长度为 3，之前建立为 O(2!*3) 或简单的 O(3!) 操作。
所以，你是对的，它应该是：
T(n+1) = T(n) + n!I(n) + O((n+1)!)
这没有出现在 list of errata 中，因此也许您应该向该页面上列出的地址发送电子邮件，看看他是否同意。