python – 递归排列打印机的时间复杂度

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?