4551
правка
Модель ввода-вывода: различия между версиями
Материал из WEGA
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
Сканирование списка из n последовательных элементов данных, очевидно, требует | Сканирование списка из n последовательных элементов данных, очевидно, требует <math>\left \lceil \frac{n}{B} \right \rceil</math> операций ввода-вывода или, в PDM, <math>\left \lceil \frac{n}{DB} \right \rceil</math> операций. Такая ''граница сканирования'' обычно определяется как «линейное количество операций ввода-вывода», поскольку она эквивалентна временной границе O(n), необходимой для выполнения того же действия во внутренней памяти. | ||
Граница сортировки sort(n) = | ''Граница сортировки'' <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]. | ||
