4551
правка
Внешние сортировка и перестановка: различия между версиями
Перейти к навигации
Перейти к поиску
м
Внешние сортировка и перестановка (посмотреть исходный код)
Версия от 12:53, 18 мая 2023
, 18 мая 2023→Нижние границы для операций ввода-вывода
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 151: | Строка 151: | ||
Предположив на данный момент, что имеется только один диск, 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 операций ввода-вывода, не превышает | Предположив на данный момент, что имеется только один диск, 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) <math>(B!)^{N/B} \bigg( N (log \; N) \binom{M}{B} \bigg). </math> | (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 | (8) <math> N \; log \; B + t \bigg( log \; N + B \; log \frac{M}{B} \bigg) = \Omega (N \; log \; N).</math> | ||
Решение для t дает подходящую нижнюю границу | Решение для t дает подходящую нижнюю границу <math>\Omega(n \; log_m \; n)</math> перестановки для случая D = 1. Общая нижняя граница (3) теоремы 2 получается в результате деления на D. | ||
Более сильную нижнюю границу можно получить в результате более тонкого рассуждения, которое считает входные операции отдельно от выходных [ ]. Для типичного случая, когда В log m = | Более сильную нижнюю границу можно получить в результате более тонкого рассуждения, которое считает входные операции отдельно от выходных [7]. Для типичного случая, когда <math>В \; log \; m = \omega (log \; N)</math>, нижняя граница ввода-вывода, вплоть до членов низшего порядка, равна <math>2n \; log_m \; n</math>. Для патологического случая, когда <math>В \; log \; m = o(log \; N)</math>, нижняя граница ввода-вывода, вплоть до членов низшего порядка, равна N/D. | ||
Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда | Поскольку перестановка – это частный случай сортировки, то, следовательно, нижняя граница перестановки применима и к сортировке. В маловероятном случае, когда <math>В \; log \; m = o(log \; n)</math>, нижняя граница перестановки составляет только £2 (N/D), и в этом случае для получения полной нижней границы (2) теоремы 1 [2] необходимо использовать модель сравнения. В типичном случае, когда B log m = J2(log n), модель сравнения для доказательства нижней границы сортировки не нужна; сложность сортировки в этом случае возникает не из-за определения порядка данных, а из-за перестановки (или маршрутизации) данных. | ||