2.3.3. Алгоритм прямоугольных разбиений

Итак, мы готовы к рассмотрению алгоритма прямоугольных разбиений. Это означает, что теперь и далее Безотносительно к числу дополнительных ячеек, необходимых для формирования строк на каждом шаге (так же, как на шаге имеем следующую теорему.

Теорема 4. Если возрастает, а убывает, то не может иметь строгого внутреннего максимума. В частности, такая упорядоченность будет минимизировать требования к объему памяти и удовлетворять условию

Доказательство. Предположим, что строгий максимум получен для , где . Тогда так что в соответствии с определением

т. e. . Из условий теоремы вытекает, что и, значит, (так как имеем дело с целыми числами). Имеем также Из леммы 2 вытекает, Это означает, что

Поскольку рассматриваются только целые числа, то

Но тогда так что , поскольку что противоре чит предположению.

Заметим, что если лемма 2 дает строгое нера венство в (2.49), даже если . Это означает, в массиве не может быть внутренних неизменяющихся участков поскольку тогда должно выполняться неравенство для некоторых

Очевидно, всегда справедливо соотношение причем равенство имеет место, когда пользуется предложенное упорядочение. Кроме того, такая

яйца является минимальной, если минимальны. Но раньше отмечалось, что является минимумом, если является максимумом, т. е. если Окончательно из леммы 2 выводим, что

Примеры. Приводимые здесь примеры показывают, что массив может иметь внутренний минимум. Кроме того, при обратном упорядочении может встретиться внутренний максимум. Следовательно, не существует обратной теоремы, дающей верхнюю границу для необходимого объема памяти.

Для того чтобы создать строки матрицы А на шаге необходимы дополнительных ячеек памяти, если (см. [2.6]).

Способы упорядочения по теореме 4 в этом случае уже не гарантируют минимума. Если, например, , то необходимое число ячеек памяти равно при но если то это число равно Поскольку из теоремы 4 можно заключить, что для данных М и

где

Метод прямоугольных разбиений обладает важным свойством, заключающимся в том, что существует непосредственная взаимосвязь между объемом памяти и требуемым числом операций ввода-вывода. Это видно из следующей теоремы.

Теорема 5. Сумма является минимальной, если убывает, а возрастает, и максимальной если возрастает, а убывает.

Доказательство. Докажем сначала первую часть посредством индукции по Пусть Введем Очевидно, тогда получаем что доказывает утверждение для

Теперь предположим, что утверждение истинно для сомножителей и рассмотрим произвольные факторизации Во-первых, переупорядочим и положим

и Тогда в соответствии с леммой Очевидно, так что по индукции имеем

Если последовательность является теперь убывающей. В противном случае положим Это дает в то время как поэтому Окончательно, если не убывает, можно применить теорему к сомножителям, чтобы получить где

Соответственно, если положим Тогда поэтому Используя утверждение для сомножителей еще раз, получим убывает, возрастает.

Вторая часть теоремы следует из аналогичных рассуждений