2.3.2. Алгоритм разбиения на квадраты

Положим Тогда имеем следующее.

Теорема 1. Пусть М и заданные целые числа, и предположим , где . Пусть и предположим, что — произвольная перестановка . Тогда

Перед тем как доказывать теорему, сделаем несколько замечаний. Вернувшись к выражениям (2.25), (2.27), обнаружим, что в соответствии с утверждением теоремы алгоритм разбиений на квадраты при заданной факторизации требует минимального объема памяти, если сомножители упорядочены по их убыванию. Тогда получим, что строки матрицы А никогда не формируются (как последовательные массивы) в ОЗУ. Но это требует выделения на шаге не более дополнительных ячеек памяти (см. [2.6]), и мы увидим, что и в этом случае упорядочение сомножителей по убыванию обеспечивает минимум. Теорема также справедлива, если что получается, если на каждом шаге формируются строки; в этом виде ее можно доказать подобным образом.

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

Примеры. Если и имеем в то время как . Задавая видим, что в то время как , т. е. это свойство не зависит от того, меньше М чем или нет. В этих двух примерах максимум достигается для максимального сомножителя. Это не всегда так при Например, если то

Однако, если то всегда достигается для последнего по порядку максимального сомножителя (см. ниже). Это утверждение, однако, неверно для массива получаемого, когда обмен выполняется на каждом шаге.

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

Теперь можно увидеть, что, так как из леммы 2 и ее следствия вытекает, что (заметим, что лемма 2 ограничивает интервалом, содержащим точно одно целое число). Кроме того, так что

Пусть [6] — массив, получаемый из помещением в начало. Тогда снова, используя следствие леммы 2, получаем Применяя лемму 1 к имеем

Эта теорема не учитывает необходимость в дополнительных ячейках памяти для формирования строк матрицы А на шаге . Для этого достаточно выделить на шаге дополнительных слов (см. [2.6]). Тогда имеем:

Следствие. Теорема 1 справедлива также для массива

Доказательство. Пусть — переупорядоченная последовательность и обозначим через соответствующий массив, для которого отыскивается максимум. Предположим также, что Тогда можно увидеть, что в соответствии с предположениями тртр, так что , следовательно, Итак, поскольку получаем Этим и доказывается следствие, так как согласно теореме

Теперь докажем тот, впрочем, достаточно очевидный факт, что наилучшая факторизация на сомножитель требует меньшего объема оперативной памяти, чем произвольная факторизация на сомножителей. Определим для данного

и положим

Теорема 2. Если М можно представить виде произведения нетривиальных сомножителей, то .

Доказательство. Пусть — оптимальная факторизация М, дающая . В соответствии с предположением, по крайней мере один сомножитель, например, может быть записан как где и — целые. Положим Из следствия леммы 2 известно, что а кроме того, из этой же леммы вытекает, что Так как получим

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

Теперь нам нужна теорема, характеризующая оптимальное разложение на сомножителей. Один результат в этом направлении дает следующая теорема.

Введем обозначение

где

Теорема 3. Предположим, что Тогда только если . Фактически, если в имеется несколько элементов с минимальной нормой то величину будут минимизировать те из них, которые встречаются реже всех.

Доказательство. В соответствии с теоремой 1 мы должны рассматривать только массивы, расположенные по убыванию. Пусть Тогда, так как лемма 2 дает

Отсюда вытекает, что в точке максимума должно быть Если два убывающих массива в такие, что то, очевидно,

так что Последняя часть теоремы вытекает из (2.25) и леммы 1, если используется расположение по убыванию

Из этой теоремы следует, что требования к памяти (для фиксированного являются минимальными, когда значения сомножителей изменяются как можно меньше. Однако это не справедливо при Если, например, то тогда как Тем не менее, как будет показано в разд. 2.4, теорему можно использовать для облегчения поиска оптимального разбиения. Теорема не справедлива, если рассматривать -нормы или массив (см. [2.6]). Можно также отметить, что даже если лучшая факторизация М могла бы удовлетворять неравенству

К сожалению, требуемое число операций ввода-вывода [см. (2.27)] не будет минимально, если сомножители упорядочены в убывающую последовательность. Если, например, , то дают соответственно. Если , то независимо от порядка сомножителей. Вообще, из леммы 2 известно, что —1, т. е.

Необходимое дополнительное число операций ввода-вывода, вызванное увеличением М до М, оказывается при не больше, чем

Это соответствует менее чем просмотрам данных.

Используя тот факт, что, начиная с шага 2, некоторые строки содержат фиктивные элементы, можно, конечно, дополнительно снизить это значение. Такая процедура, однако, усложнит реализацию алгоритма.

Заслуживает упоминания частный случай, когда М и могут быть представлены в виде Такое разбиение даст в результате число операций ввода-вывода, точно равное независимо от значения сомножителей. Если т. е. если не требуется дополнительного объема памяти на шаге даже если формируются строки матрицы А.

теоремы 3 следует, что такое упорядочение требует оптимального числа ячеек памяти, равного . В то же время необходимое число операций ввода-вывода будет меньше, чем требуется

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

Примеры. Пусть . Тогда факторизация дает в обоих случаях объем памяти, равный 360. При этом число операций ввода-вывода равно 442 и 372 соответственно. Если, с другой стороны, получаем и 130, тогда как и 180 соответственно.