1-лекция: Введение в проектирование алгоритмов. Усовершенствованные методы разработки и анализа алгоритмов

Технология проектирования алгоритма

• На практике восходящая раз­работка в чистом виде невозможна; построение каждого но­вого элемента должно сопровождаться «просмотром вперед» с целью проверки, выполняются ли все требования, предъ­являемые к разрабатываемой программе. Но даже при таком подходе на более позднем этапе часто обнаруживается, что использованная ранее последовательность построения была выбрана неправильно и требует корректировки.
• Таким образом, на практике при разработке алгоритмов обычно используется сочетание методов нисходящего и вос­ходящего проектирования.

Технология проектирования алгоритма

• Использование вышеназванных методов позволило соз­дать огромное количество разнообразных алгоритмов, и пришлось обратить серьезное внимание на вопросы их эф­фективности. В значительной степени эффективность алгоритма зависит от его сложности — количественной характе­ристики, указывающей, сколько времени работает алгоритм (временная сложность) либо какой объем памяти необходим для его выполнения (емкостная сложность). Сложность рас­сматривается в основном для алгоритмических моделей, по­скольку в них время и память присутствуют в явном виде.

Сложность алгоритма

Сложность алгоритма

• Физическое время выполнения алгоритма — это величина, равная произведению n и t, где и число действий (элемен­тарных шагов, команд); t — среднее время выполнения одно­го действия. Число шагов и определяется описанием алго­ритма в данной алгоритмической модели и не зависит от физической реализации модели; t— величина физическая и зависит от скорости сигналов в элементах и узлах ЭВМ, По­этому объективной математической характеристикой трудо­емкости алгоритма (его временной сложности) в данной мо­дели является число действий.

Использованная литература:

• Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн «Алгоритмы. Построение и анализ» Вильямс, 2013 год, 1324 стр. Издание 3-е
• http://www.math.nsc.ru/LBRT/k5/OR-MMF/Kleinberg_Tardoc_algoritmy_razrabotka_i_primenenie.pdf
• https://e-maxx.ru/bookz/files/cormen.pdf
• https://studfile.net/preview/5535319/page:24/

• Спасибо за внимание!