递归置换prin的时间复杂度

Question

在解释recursive algorithms to generate permutations in lexicographic order时，我提供了一个简单的算法：

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!)。在

（灵感来自前面的一个问题：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

我不知道什么是“python”式的方法，但我认为将一个序列（以数组形式给出）转换为下一个字典排列可能比递归构造它更容易（尤其是在集合和排序中有多个删除）。下一个排列可以在线性时间中找到，如下所示：

• 找到降序后缀（从末尾向后进行线性扫描）
• 如果后缀前面有符号（相当于测试当前位置是否大于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

优点：

• 正在处理就地-不需要额外的集合副本（变量done、remaining、sorted\rem）
• 不分类收集，不删除（删除后压缩）
• 没有递归及其堆栈消耗
• 轻松访问结果-无需修改代码来将print(done)替换为任何其他use(done)