Какова сложность памяти в std :: sort () и std :: sort_heap ()?
Как в названии — какова сложность памяти std::sort() а также std::sort_heap()? (Последнее требует std::make_heap() так что я хотел бы знать, насколько сложна его память.)
Я пробовал искать на этих сайтах: http://www.cplusplus.com/reference/ http://en.cppreference.com/w/ но либо я пропустил это, либо они упоминают только временную сложность. Указана ли где-либо сложность памяти указанных функций (в стандарте C ++ или в каком-либо другом документе)? Или, может быть, это зависит от реализации?
Решение
За std::sort() Я нашел ответ на Cboard, который в значительной степени говорит:
Качество реализации вопроса. Различные реализации используют память более эффективно, чем другие реализации. Помимо этого, стандарт допускает специализации для
std::sortдля разных категорий итераторов, позволяющих реализации выбирать между несколькими различными вариантами, если сложность (время) соответствует требованиям. Приведенная сложность — это даже не время, а количество сравнений. Реализация может выполнять операции обмена N³.
Затраты памяти для большинства реализаций std::sort будет связано с глубиной рекурсии и количеством локальных переменных, хранящихся в стеке для каждого уровня рекурсии. Реализация HP / Microsoft STL std::sort использует Quicksort до тех пор, пока не обнаружит, что уровень рекурсии становится слишком глубоким, и в этом случае он переключается на сортировку кучи. Если размер небольшой, например 32 или меньше, он использует Insertionsort.
Вы можете увидеть сравнение алгоритмов, в Википедии страница и оценить сложность памяти.
Точно так же я подозреваю, что два других алгоритма попадают в один и тот же случай.
Другие решения