4446
правок
Внешние сортировка и перестановка: различия между версиями
Материал из WEGA
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 12:49, 18 мая 2023
, 18 мая 2023→Нижние границы для операций ввода-вывода
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 146: | Строка 146: | ||
== Нижние границы для операций ввода-вывода == | == Нижние границы для операций ввода-вывода == | ||
Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [ ]. Идея доказательства состоит в том, чтобы для каждого t > | Следующее доказательство нижней границы перестановки (3) теоремы 2 принадлежит Аггарвалу и Виттеру [2]. Идея доказательства состоит в том, чтобы для каждого <math>t \ge 0</math> вычислить число различных упорядочений, которые реализуются последовательностями из t операций ввода-вывода. Значение t, при котором число различных упорядочений впервые превышает N!/2, является нижней границей среднего числа операций ввода-вывода (и, следовательно, числа таких операций в наихудшем случае), необходимых для выполнения перестановки. | ||
Предположив на данный момент, что имеется только один диск, D = 1, рассмотрим, как может измениться количество реализуемых упорядочений в результате ввода-вывода. С точки зрения увеличения числа реализуемых упорядочений, эффект от чтения дискового блока значительно больше, чем от его записи, поэтому достаточно рассмотреть только эффект от операций чтения. Во время операции чтения в блоке чтения имеется не более B элементов данных, и они могут быть размещены среди М элементов во внутренней памяти не более чем | Предположив на данный момент, что имеется только один диск, D = 1, рассмотрим, как может измениться количество реализуемых упорядочений в результате ввода-вывода. С точки зрения увеличения числа реализуемых упорядочений, эффект от чтения дискового блока значительно больше, чем от его записи, поэтому достаточно рассмотреть только эффект от операций чтения. Во время операции чтения в блоке чтения имеется не более B элементов данных, и они могут быть размещены среди М элементов во внутренней памяти не более чем <math>\binom{M}{B}</math> способами, поэтому число реализуемых упорядочений увеличивается в <math>\binom{M}{B}</math> раз. Если блок никогда ранее не находился во внутренней памяти, то число реализуемых упорядочений увеличивается на дополнительный коэффициент В!, поскольку элементы в блоке могут быть переставлены между собой. (Этот дополнительный вклад B! может иметь место только один раз для каждого из N/B исходных блоков). Существует не более <math>n + t \le N \; log \; N</math> способов выбрать, какой дисковый блок участвует в t-й операции ввода-вывода (при произвольном объеме дискового пространства). Следовательно, число различных упорядочений, которые могут быть реализованы всеми возможными последовательностями t операций ввода-вывода, не превышает | ||
(7) | (7) <math>(B!)^{N/B} \bigg( N (log \; N) \binom{M}{B} \bigg). </math> | ||
Положив, что выражение в (7) не меньше N!/2, и упростив его за счет взятия логарифма, получаем результат | Положив, что выражение в (7) не меньше N!/2, и упростив его за счет взятия логарифма, получаем результат | ||
8 <math> N \; log \; B + t | |||
Решение для t дает подходящую нижнюю границу Q(n\ogm n) перестановки для случая D = 1. Общая нижняя граница (3) теоремы 2 получается в результате деления на D. | Решение для t дает подходящую нижнюю границу Q(n\ogm n) перестановки для случая D = 1. Общая нижняя граница (3) теоремы 2 получается в результате деления на D. | ||
