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

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

(受此处较早的 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! 时真正重要的。