在尝试解释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?

解决方法:

我相信有一个证据表明运行时确实是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！).

这也证明了排序等的运行时间无关紧要,只要它们是多项式,该算法将是渐近最优的.

常量可能会很糟糕,这就是处理n * n！时真正重要的事情.