Как stable_partition является адаптивным алгоритмом?

stable_partition - это шаблон функции, присутствующий в заголовочном файле алгоритма C++ STL. Я читал, что это адаптивный алгоритм, и его временная сложность составляет O(n*logn) или O(n) в зависимости от некоторых факторов. Может кто-нибудь объяснить мне, каковы эти факторы и как сложность времени зависит от этих факторов. Благодарю вас!

Источник

3 ответа

Решение

Это зависит от того, сколько памяти доступно.

Если у вас достаточно памяти, один из способов - просто создать достаточно большой буфер, вставить соответствующие элементы спереди и сзади и положить его обратно в оригинал, когда закончите. Это займет O(N) время.

Если памяти недостаточно, на этой странице упоминается подход O(n log n) на месте (также может быть и другой подход) - если вы хотите переставить - на фронт и + сзади вы неоднократно находите подмассивы в виде ++++--- и переставить это (стабильно), чтобы ---++++ (что можно сделать с 3-мя реверсами - полностью изменить весь подмассив, затем отрицательную часть, затем положительную часть).

Физическая проверка на достаточное количество памяти может быть просто сделана путем попытки выделить память и проверить ее на наличие ошибок. Один из способов сделать это с new, который может либо бросить std::bad_alloc или вернуть нулевой указатель, в зависимости от используемой версии, если он не выделяет память.

Источник

Есть 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 это медленный алгоритм.

Источник

Смотрите здесь:

Точно последние приложения предиката и самое большее (последний-первый)*log(последний-первый) подкачки, если недостаточно памяти или линейное число перестановок, если достаточно памяти.

Источник
Другие вопросы по тегам