Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

f or все другие э л е м е н ты хш8 d o i f x>MAX thenMAX^ x ; end. В результате n-\ сравнений найдётся наибольший элемент. Заметим, что не учитывается время на выборку элемента. Далее начинается поиск наименьшего элемента по аналогичному алгоритму. Если считать эти процедуры независи­ мыми, то вновь потребуется п-\ сравнений. В итоге для нахождения наиболь­ шего и наименьшего элементов из S потребуется 2п-2 сравнений. Число необходимых сравнений можно уменьшить, если использовать принцип «разделяй и властвуй», который в теории алгоритмов называют стра­ тегией дублирования. Стратегия дублирования состоит в следующем. Пусть размер задачи (раз­ мер входных данных задачи) равен п. Разобьём задачу на две подзадачи размера п/2 той же структуры, что и исходная задача. Если решения этих задач можно скомбинировать в решение исходной задачи, то получится эффективный алго­ ритм. Рассмотрим, как стратегия дублирования даёт ускорение для решения пре- дыдуш,ей задачи. Положим, что число элементов множества S является степе­ нью числа 2, т.е. п=2^, для некоторого к, к>\. Реализуем рекурсивный поиск, при котором множество S разбивается по­ следовательно на два подмножества по следуюш,ей процедуре MAXMIN. procedure MAXMIN(5'): 1 . i f I S I =2 then begin 2. пусть 5"= {(2,/)}; 3. return(MAX(<2,/)),MIN(<2,/))) end else begin 4. разбить S на подмножества Si и S2, такие, что n{Si) = n{S2); 5. {maxl, minl)<r-MAXMIN{Si); 6. (maxl, /77ш2)^ МАХМ1К (5'2); 7. return(MAX(/77<2x7, max2). МШ{тт1, min2)) end В этой процедуре сравнения происходят только на третьем шаге, где срав­ ниваются два элемента множества S, из которых оно и состоит, и на шаге 7, где сравниваются maxl с тах2 и mini с min2. Пусть Т(п) - число сравнений элемен­ тов множества S. Ясно, что Т{2)=\. Если п >2, то Т(п) - обш,ее число сравнений, произведённых в двух вызовах процедуры MAXMIN (строки 5 и 6), работаю- ш,их на множествах размера п/2 и еш,ё два сравнения в строке 7. Таким образом: 223