stable_partition如何成为自适应算法？

Question

stable_partition是c ++ STL的算法头文件中存在的函数模板.我读到它是一种自适应算法,其时间复杂度为O(n*logn)或O(n),具体取决于某些因素.有人可以解释一下这些因素是什么以及时间复杂度如何取决于这些因素.谢谢 !

Answer 1

有2个实现.

1. "慢"的O(n*logn)实施
2. "更快"的O(n)实施

然而,快速实现需要使用大量可能无法使用的内存.因此,stable_partition如果有足够的可用内存,则询问操作系统,然后在两个实现之间进行选择.

以下是gcc 4.8.1实现中的一些示例,其中包含一些注释:

template<typename _ForwardIterator, typename _Predicate>
    _ForwardIterator
    stable_partition(_ForwardIterator __first, _ForwardIterator __last,
             _Predicate __pred)
    {
       ...
       ...

       /// Try to allocate enough memory for the faster algorithm
      _Temporary_buffer<_ForwardIterator, _ValueType> __buf(__first, __last);

    if (__buf.size() > 0)  /// If there is enough memory
      return
        std::__stable_partition_adaptive(__first, __last, __pred,
                      _DistanceType(__buf.requested_size()),
                      __buf.begin(),
                      _DistanceType(__buf.size()));
    else  /// If there is not enough memory
      return
        std::__inplace_stable_partition(__first, __pred,
                     _DistanceType(__buf.requested_size()));
    }

这std::__stable_partition_adaptive是快速算法,std::__inplace_stable_partition是慢速算法.

Answer 2

这取决于有多少可用内存。

如果你有足够的内存，一种方法是简单地创建一个足够大的缓冲区，从前面和后面插入相应的元素，完成后将其放回原来的元素。这将花费 O(n) 时间。

如果没有足够的内存，本页提到了 O(n log n) 就地方法（也可能还有另一种方法） - 如果您想重新排列-到前面和+后面，您可以重复在中查找子数组形式++++---并将其（稳定地）重新排列为---++++（可以通过 3 个反转来完成 - 反转整个子数组，然后反转负数部分，然后反转正数部分）。

物理检查是否有足够的内存可以简单地通过尝试分配内存并检查是否失败来完成。实现此目的的一种方法是使用 a new，如果无法分配内存，它可以抛出一个std::bad_alloc或返回一个空指针，具体取决于所使用的版本。