我想了解next_permutation函数的时间复杂度。我能看到它的代码吗？
1个回答
12
参见http://www.sgi.com/tech/stl/next_permutation.html：
线性。最多需要（last - first）/ 2次交换。
要查看源代码，只需查找您系统的STL头文件即可。在类Unix系统上，您可能需要在/usr/include/c++/4.1.2/bits/stl_algo.h之类的位置进行查找。
- Oliver Charlesworth
1
3实际上，它比线性更好。它是摊销O（1） - 也就是说，如果你调用它n！次，它仅需要O（n！）次操作，而不是n * n！。请参阅此问题。 - ShreevatsaR
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
- 相关问题
- 3 C++23中，std::string::contains的时间复杂度是什么？
- 128 std::next_permutation实现解释
- 6 std::queue::size的时间复杂度是什么？
- 23 std::map的时间复杂度是什么？
- 4 C++ : "reset" std::next_permutation()
- 21 std::next_permutation的摊销复杂度是什么？
- 51 C++标准库中的std::sort()函数的时间复杂度是什么？
- 5 std::set中的std::lower_bound函数的时间复杂度是多少？
- 14 C++中的strstr()函数的时间复杂度、空间复杂度和算法是什么？
- 5 std::hash<string>的时间复杂度是什么？