c ++中std :: next_permutation()函数的时间复杂度是多少？

Question

我想知道next_permutation函数的时间复杂度.我也可以查看它的代码吗？

Answer 1

线性.最多(最后 - 第一)/ 2次互换.

要查看源代码,只需查看系统的STL头文件.在类Unix系统上,你可能需要看起来像/usr/include/c++/4.1.2/bits/stl_algo.h.

实际上,它比线性更好.它是摊销的O(1) - 即,如果你称之为n!次,它只需要O(n!)次操作,而不是n*n!.见[this question](http://stackoverflow.com/questions/4973077/the-amortized-complexity-of-stdnext-permutation). (3认同)