Алгоритмы без использования дополнительной памяти

Воскресенье, 14 сентября 2014, 13:00–14:35
ПОМИ РАН

Описание

  • Сравнение разных сортировок (heap, merge, quick, introsort, insertion, selection)

  • reverse за \(O(n)\), rotate за \(O(n)\), sort за \(O(nlogn)\), stable sort за \(O(n^2)\).

  • inplace-merge: стабильный за \(O(n+m^{1+eps})\), стабильный за \(O(nlogn)\), нестабильный за \(O(n)\)

  • merge-sort: нерекурсивная версия за \(O(nlogn)\), inplace версия за \(O(nlog^2n)\)

  • BlockSort: buffer extraction + sort blocks + local merges

  • Обзор структур данных без доп.памяти: heap, k-heap, min-max-heap, fenwick-tree, beap