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

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