java - 分词和排列之间的时间复杂度差异

Question

Word Break - Recurrence

上一篇文章的解释是有道理的。但为什么不能是 T(n) = nT(n-1) + 1 呢？结果是 n!。我做错了什么？

这与排列递归有何不同，Permutation - recursion

Answer 1

不同之处在于 Permutation ，假设我们有一个序列 a,b,c,d ，对于第一步，我们可以选择所有这些，这使得我们的第一步有 n的可能性。之后，对于第二步，我们还有 n-1每一步的可能性。所以我们有n*(n-1)... 。

虽然在 Word Break ，正如链接中的悲伤，免得说我们有一个 abcd 的序列我们有一个单词列表 a,b,c,d,ab,ac,ad,bc,bd,cd,... 。我们还有n第一步选择:a,ab,abc,abcd 。但之后，我们就没有 n-1选择每一步。例如，如果我们选择 abcd作为第一步，我们根本没有第二步。