2.3.4. О преимуществах введения единичного сомножителя

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

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

Утверждение 2. Пусть . Тогда, если для некоторого существуют разбиения для которых

Такое же утверждение можно сделать, если

Доказательство. Если , то новые разбиения задаются значениями Поскольку , требования к объему памяти будут определяться

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

Если положим и сохраним остальные сомножители, чтобы получить тот же самый результат