4. способы повышения эффективности алгоритмов

2. пусть s={a,b};
3. return ( MAXEL(a,b), MINEL(a,b) )
end
else
begin
4. разбить S на два равных подмножества S1 и S2
5. (max1, min1)MAXMIN(S1);
6. (max2, min2)MAXMIN(S2);
7. return (MAXEL(max1, max2),MINEL(min1, min2) )
end;

Пусть Т(n) - число сравнений элементов множества S, которые надо произвести в процедуре MAXMIN, чтобы найти наибольший и наименьший элементы n-элементного множества. Ясно, что Т(2)=1. Если n>2, то Т(n) - общее число сравнений, произведенных в двух вызовах процедуры MAXMIN (строки 5 и 6), работающей на множестве размера n/2 и еще два сравнения в строке 7. Таким образом,

Решением рекуррентных уравнений (4.18) служит функция Т(n)=3n/2 - 2, что можно доказать индукцией по n.
Можно показать, что для одновременного поиска наибольшего и наименьшего элементов n-элементного множества надо выполнить не менее 3n/2 - 2 сравнений его элементов. Следовательно,алгоритм 4.3 оптимален в смысле числа сравнений между элементами из S, когда n есть степень числа 2.
Временная сложность процедуры определяется числом и размером подзадач и в меньшей степени работой, необходимой для разбиения данной задачи на подзадачи. Так как рекуррентные уравнения вида (4.18) часто возникают при анализе рекурсивных алгоритмов типа “разделяй и властвуй”, рассмотрим решение таких уравнений в общем виде.
Теорема 4.1 Пусть a, b, c - неотрицательные постоянные. Решением рекуррентных уравнений вида

где n- степень числа с,имеет вид

Из теоремы вытекает, что разбиение задачи размера n (за линейное время) на две подзадачи размера n/2 дает алгоритм сложности О(nLog₂n). Если бы подзадач было 3, 4 или 16, то получился бы алгоритм сложности порядка , n² или n⁴ соответственно. С другой стороны, разбиение задачи на 4 подзадачи размера n/4 дает сложность порядка nlog₂n, а на 9 и 16 - порядка и n² соответственно.
Если n не является степенью числа С, то обычно можно вложить задачу размера n в задачу размера n', где n' - наименьшая степень числа С, большая n. Поэтому порядки роста, приведенные в теореме 4.1, сохраняются для любого n. На практике часто можно разработать рекурсивные алгоритмы, разбивающие задачи произвольного размера на С равных частей, где С велико, насколько возможно. Эти алгоритмы, как правило, эффективнее(на постоянный множитель) тех, которые получаются путем представления размера входа в виде ближайшей сверху степени числа С.