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

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

Возможно, наибольший интерес представляет граница перестановки, а именно – стоимость перегруппировки n элементов в заданном порядке, составляющая @(min(sort(n), n)) [1] или @(min(sort(n), n/D)) в модели PDM [ ]. Для всех практических целей она совпадает с границей сортировки. Отметим контраст с использованием внутренней памяти, при котором с поправкой на константный коэффициент перестановка имеет ту же стоимость, что и линейное сканирование. Поскольку почти все нетривиальные алгоритмические задачи включают задачу перестановки, в результате только самые простые задачи могут быть решены при помощи O(scan(n)) операций ввода-вывода; большинство задач требуют £?(perm(n)), что, в сущности, представляет собой нижнюю границу J2(sort(n)). Таким образом, в то время как алгоритмы на базе внутренней памяти, стремящиеся к линейному времени, должны максимально избегать использования сортировки как инструмента, алгоритмы на базе внешней памяти могут использовать сортировку, не опасаясь значительного превышения нижней границы. Это делает разработку оптимальных алгоритмов на базе ввода-вывода потенциально более простой, чем разработка алгоритмов на базе внутренней памяти. Однако это компенсируется тем обстоятельством, что, в отличие от работы во внутренней памяти, граница сортировки не равна границе поиска, умноженной на n, из чего следует, что алгоритмы, основанные на опросе поисковой структуры на базе дерева O(n) раз, обычно не сводятся к эффективным с точки зрения операций ввода-вывода алгоритмам. Буферные деревья [ ] обеспечивают амортизированную границу поиска в O((1/B)logM/B(N/B)) операций ввода-вывода, но могут использоваться только в случае, если вся последовательность обновлений и запросов известна заранее, и потому представляют собой ограниченное решение данной задачи.