Модель ввода-вывода: различия между версиями

''Граница сортировки'' <math>sort(n) = \Theta \bigg( ( \frac{n}{B}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) </math> операций ввода-вывода обозначает стоимость сортировки n элементов, использующей только сравнения. Таким образом, она эквивалентна границе сортировки во внутренней памяти, составляющей <math>\Theta (n \; log \; n)</math>. В модели PDM граница сортировки составляет <math>\Theta \bigg( ( \frac{n}{DB}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) </math>. Эта граница может быть достигнута при помощи различных алгоритмов сортировки, включая алгоритмы внешнего слияния [1, 6] и сортировки распределением [1, 5].

Возможно, наибольший интерес представляет ''граница перестановки'', а именно – стоимость перегруппировки n элементов в заданном порядке, составляющая <math>\Theta (min(sort(n), n)) \;</math> [1] или <math>\Theta (min(sort(n), \frac{n}{D})) \;</math> в модели PDM [10]. Для всех практических целей она совпадает с границей сортировки. Отметим контраст с использованием внутренней памяти, при котором с поправкой на константный коэффициент перестановка имеет ту же стоимость, что и линейное сканирование. Поскольку почти все нетривиальные алгоритмические задачи включают задачу перестановки, в результате только самые простые задачи могут быть решены при помощи <math>O(scan(n)) \;</math> операций ввода-вывода; большинство задач требуют <math>\Omega (perm(n)) \;</math>, что, в сущности, представляет собой нижнюю границу <math>\Omega (sort(n)) \;</math>. Таким образом, в то время как алгоритмы на базе внутренней памяти, стремящиеся к линейному времени, должны максимально избегать использования сортировки как инструмента, алгоритмы на базе внешней памяти могут использовать сортировку, не опасаясь значительного превышения нижней границы. Это делает разработку оптимальных алгоритмов на базе ввода-вывода потенциально более простой, чем разработка алгоритмов на базе внутренней памяти. Однако это компенсируется тем обстоятельством, что, в отличие от работы во внутренней памяти, граница сортировки ''не'' равна границе поиска, умноженной на n, из чего следует, что алгоритмы, основанные на опросе поисковой структуры на базе дерева O(n) раз, обычно не переводятся в эффективные с точки зрения операций ввода-вывода алгоритмы. [[Буферные деревья]] [3] обеспечивают амортизированную границу поиска в <math>O \bigg( ( \frac{1}{B}) \; log_{\frac{M}{B} } \; (\frac{n}{B}) \bigg) </math> операций ввода-вывода, но могут использоваться только в случае, если вся последовательность обновлений и запросов известна заранее, и потому представляют собой ограниченное решение данной задачи.