g++ 内存——内存总量：484412 kB msvc++ 内存——内存总量：484412 kB 平台—— Windows XP Pro 编译器—— Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 13.10.3077 for 80×86 Copyright (C) Microsoft Corporation 1984-2002. All rights reserved local 内存——内存总量：484412 kB 平台—— Windows XP Pro 编译器—— g++ (GCC) 4.1.1 20060525 (Red Hat 4.1.1-1) Copyright (C) 2006 Free Software Foundation, Inc. 这是一个免费软件，可以查看源代码进行复制，未经授权不得用于商业或者其他特殊目的。 push pop modify erase join std::priority_queue [std note 2]与 [std note 1] 一样，也不是算法的属性，而是与STL实现相关。同样，如果优先级队列采用std::vector实现，也可以将复杂度降低到Θ(n)，但是，是一个非常大的常数（必须调用std::make_heap，这个操作是一个开销很大的线性操作）；如果优先级队列用std::deque实现，则不可能降低复杂度。 [thin_heap_note] 一个稀疏堆，最坏情况的修改时间总是为&Theta(log(n))，但是摊销时间依赖于操作的特性：I）如果是插入较大的key值（从优先队列的比较函数角度来看），摊销时间是O（1）。但是如果II）插入一个较小的key值，那么摊销时间和最坏的情况下是一样的。注意：在大多数算法中，I）很重要，II）并不重要。 摊销push和pop操作 如上表所示，受限制最小的底层数据结构是二叉堆和配对堆。因此，也就不奇怪他们在摊销常数上表现最好。 std::
Read full article from 优先队列的性能测试 - 博客 - 伯乐在线
No comments:
Post a Comment