Математическая логика и теория алгоритмов

в результате п-1 сравнений найдется наибольший элемент. Заметим, что не учитывается время на выборку элемента. Далее начи­ нается поиск наименьшего элемента по аналогичному алгоритму. Если считать эти процедуры независимыми, то вновь потребуется п-\ сравнений. В итоге для нахождения наибольшего и наименьшего элементов из S потребуется 2п-2 сравнений. Число необходимых сравнений можно уменьшить, если использовать принцип «разделяй и властвуй», который в теории алго­ ритмов называют еще стратегией дублирования. Стратегия дублирования состоит в следующем. Пусть размер задачи (размер входных данных задачи) равен п. Разобьем задачу на две подзадачи размера и/2 той же структуры, что и исходная задача. Если решения этих задач можно скомбинировать в решение исходной задачи, то получится эффективный алгоритм. Рассмотрим, как стратегия дублирования дает ускорение для ре­ шения предыдущей задачи. Положим, что число элементов множества S является степенью числа 2, т.е. п-2'', для некоторого к, й:>1. Реализуем рекурсивный поиск, при котором множество S разби­ вается последовательно на два подмнолсества по следующей процеду­ ре МАХМП^. procedure MAXMTN( »S): 1) if I S 1=2 then begin 2) пусть S={a,b}\ 3) return(MAX(a,b),MlN(a,b)) end else begin 4) разбить S на два равных подмножества Si и Si, 5) (niaxl, miiil)'<-MAXMIN(iSi); 6) (max2, min2)<-MAXMIN(S'2); 7) return(MAX(maxl, max2). MIN(minl, min2)) end 283