递归置换打印机的时间复杂度

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()

First question: It seems a bit wasteful to me and I wonder what the time complexity it really has, given a pythonic implementation like this?

请注意，最佳时间复杂度为 O(n * n!)，因为我们需要打印 n！大小 n.

的排列

我猜是因为排序（我假设是 python 中的 O(n log n)），将添加一个额外的 log n 因子（我认为这对于n 我们可以将此程序用于）。

问题的第二部分，稍微优化一下。

Second question: Assuming that we can implement sorted in O(n) time, and append, remove and del[-1] in O(1) time, what would be the resulting time complexity?

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! 时真正重要的。

Answer 2

我不知道 'pythonic' 做事的方式，但我想将一个序列（在数组中给出）转换为下一个字典顺序排列可能比递归构造它更容易（尤其是从集合中删除多次和排序）。可以在线性时间内找到下一个排列，如下所示：

求降序后缀（从末尾向后线性扫描）
如果后缀前面有一个符号（相当于测试当前pos是否大于0）
- 将其与后缀中最小的大符号交换（线性扫描或bsearch）
反转后缀（线性）

下面是五个示例过程的简单可视化。横条表示后缀位置。

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

优点：

处理就地 - 不需要额外的集合副本（变量完成，剩余，sorted_rem）
不对集合进行排序，也不删除（删除后压缩）
没有递归及其堆栈消耗
轻松访问结果 - 无需修改用于将 print(done) 替换为任何其他 use(done)

递归置换打印机的时间复杂度

Time complexity of recursive permutation printer

python

algorithm

permutation

time-complexity