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

Несколько границ сложности особенно важны практически для всех алгоритмов и структур данных, эффективных с точки зрения модели ввода-вывода. ''Граница поиска'' в <math>\Theta (log_B \; n)</math> операций ввода-вывода, достижимая при использовании [[B-дерево (дерево многоканального поиска)|B-дерева]] [4], равна стоимости поиска элемента в упорядоченном наборе из n элементов, использующего только сравнения.

Сканирование списка из n последовательных элементов данных, очевидно, требует <math>\left \lceil \frac{n}{B} \right \rceil</math> операций ввода-вывода или, в PDM, <math>\left \lceil \frac{n}{DB} \right \rceil</math> операций. Такая ''граница сканирования'' обычно определяется как «линейное количество операций ввода-вывода», поскольку она эквивалентна временной границе O(n), необходимой для выполнения того же действия во внутренней памяти.

''Граница сортировки'' <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].