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

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

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

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

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

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

Существует 2 реализации .

  1. «медленная» реализация O(n*logn)
  2. «более быстрая» реализация O(n)

Однако для быстрой реализации требуется много памяти , которая может быть недоступна. Таким образом, stable_partition запрашивает операционную систему, если доступно достаточно памяти, а затем выбирает между двумя реализациями.

Вот пример из реализации gcc 4.8.1 с некоторыми моими комментариями:

 template _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 – медленный алгоритм.

См. Здесь :

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