2.3. Оптимизация эффективности алгоритма

2.3.1. Две леммы

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

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

Лемма 1. Последовательность является возрастающей.

Доказательство. По определению, Следовательно, умножение на дает

Эта лемма просто устанавливает, что в алгоритме разбиения на квадраты длина строк увеличивается.

Лемма

Доказательство. Используем индукцию по числу сомножителей Имеем

В первом случае справедливость леммы очевидна, во втором надо только заметить, что

Предположим, что неравенство справедливо для сомножителей, т. е.

Запишем где . Тогда и

Используя левое неравенство из (2.35), находим

С другой стороны, если то

Далее, если можно записать

Отсюда непосредственно вытекает следующее.

Следствие. Так как — целое, инвариантны относительно изменения факторизации . В частности, можно переставить.

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