c++ - Visual Studio 中 priority_queue::push() 的时间复杂度？

Question

我使用 Windows 和 Visual Studio 2015。据我从引用资料和其他人的问题中可以看出，priority_queue::push() 应该具有 O(log(n)) 时间复杂度。这当然意味着这个简单的代码:

#include <queue>
using namespace std;
int main()
{
    priority_queue<int> q;
    const int n=100000; //We can vary this
    for (int i = 0; i < n; i++)
    {
        q.push(i);
    }
}

应该有复杂度 O(nlog(n))，这意味着对于 n=100 000 如上所述，它应该是小菜一碟。这对我来说需要几分钟(与 std::set 相同的事情只需要一秒钟)。

我已经调试了这段代码并在 10 秒的倍数处停止了它，并绘制了那些时间的 i 的平方。它们非常(!)准确地位于一条线上，这意味着上述代码的复杂度为 O(n^2)。

我的问题是，priority_queue::push() 不能保证在 O(log(n)) 内运行，还是我做错了什么？

提前致谢!

编辑: 我试过 this post 中的提示.它没有改善任何事情，所以我想重新分配底层容器不是我的问题。

编辑:已解决 与往常一样，答案非常简单。我在 Debug模式下运行程序，这显然改变了某些功能的复杂性。我不知道这一点，虽然我认为这是很合理的......

Answer 1

答案是否定的，它根本不能保证在 O(log(n)) 内运行。这种保证是不可能实现的。