递归排列打印程序的时间复杂度

Question

在试图解释生成字典序排列的递归算法时，我提供了这个简单的算法：

def permute(done, remaining):
  if not remaining:
    print done
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

def main():
  permute([], [1,2,3,4])

if __name__ == "__main__":
  main()

第一个问题：对于像这样的Python实现，我觉得它有点浪费，我想知道它的时间复杂度到底是多少？请注意，最优的时间复杂度将是O(n * n!)，因为我们需要打印大小为n的n!个排列。

我猜测由于排序（我假设在Python中是O(n log n)），会添加一个额外的log n因子（我认为对于我们可以使用该程序的n来说，这在实际上是可以忽略不计的）。

第二个问题：假设我们可以在O(n)时间内实现排序，并且在O(1)时间内实现append，remove和del[-1]，那么结果的时间复杂度将是多少？

- Programmer Person

Answer 1

我相信有证据表明运行时间确实是 O(n*n!)。

（受此前的一个SO问题启发：complexity of recursive string permutation function）

我们有以下递归式，不打印时花费的时间： T(n) = n*T(n-1) + O(n^2) 现在如果 U(n) = T(n)/n!，那么我们必须有 U(n) = U(n-1) + O(n^2/n!) 这是一个望远镜式的级数。

因此，我们得到 U(n) = U(1) + 2^2/2! + 3^2/3! + ... + n^2/n! 使用 e^x 的幂级数，将其乘以 x 并进行几次导数，我们可以看到 2^2/2! + 3^2/3! + ... + n^2/n! = O(1) 因此，

T(n) = O(n!)。

因此，这是没有打印输出所花费的时间。

因此，具有打印输出的总时间为O(n * n!)。

这也证明了无论sorted等的运行时间如何，只要它们是多项式的，该算法就会渐近地最优。

常数可能很糟糕，这实际上是处理n*n!时需要考虑的问题。

- Programmer Person

Answer 2

我不知道“Pythonic”的做法，但我觉得将一个序列（以数组的形式给出）转换为下一个字典序排列可能比递归构造更容易（特别是在从集合中进行多个删除和排序时）。下一个排列可以像这样在线性时间内找到：

• 找到降序后缀（从末尾向前进行线性扫描）
• 如果后缀前面有一个符号（等同于测试当前位置是否大于0）
  • 将其与后缀中最小的大符号交换（线性扫描或二分查找）
• 反转后缀（线性）

以下是五个示例的简单可视化。 竖杠表示后缀位置。

12345 - 1234|5 - 1235|4 - 1235|4 - 12354
13452 - 134|52 - 135|42 - 135|24 - 13524
35421 - 3|5421 - 4|5321 - 4|1235 - 41235
54312 - 5431|2 - 5432|1 - 5432|1 - 54321
54321 - |54321 - |54321 - |12345 - 12345

优点：

• 原地处理 - 不需要额外复制集合（变量 done，remaining，sorted_rem 已完成）
• 无需对集合进行排序和删除（以及删除后的压缩）
• 没有递归，不会消耗堆栈
• 易于访问结果 - 无需修改代码以将 print(done) 替换为任何其他 use(done)

- CiaPan