12. Временная и ёмкостная сложности алгоритмов.
Временная сложность алгоритма – время T, необходимое для его выполнения. Оно равно произведению числа элементарных шагов алгоритма на среднее время выполнения одного шага, T = kt. Поскольку t зависит от исполнителя, реализующего алгоритм, то считают, что сложность алгоритма зависит от k.
Емкостная сложность алгоритма выражается количеством единиц памяти, требуемой для его реализации. Она не может расти быстрее временной сложности, т.к. на использование каждой дополнительной единицы памяти потребуется дополнительное время. Поэтому часто ограничиваются рассмотрением лишь временной сложности.
На практике сложность алгоритма указывают как функцию от размера обрабатываемых данных (n). Если имеет место линейная зависимость, то сложность алгоритма называется линейной и записывается O(n), читается «О большое от n».
O(n2) – квадратичная сложность, O(n3) – кубическая, …
Время выполнения алгоритма может зависеть кроме размера и от набора данных, в таком случае различают:
максимальную сложность Тmax(n) – время выполнения алгоритма в том случае, когда выбранный набор n данных наиболее увеличивает срок выполнения алгоритма.
среднюю сложность Тср(n) – среднее время выполнения алгоритма, примененного к n произвольным данным.
Сложность задачи – сложность наилучшего алгоритма, известного для ее решения, она зависит от уровня развития методов решения.
13. Графическое описание алгоритмов. Блоки описания алгоритмов.
В связи с трудностями, возникающими в процессе проектирования программы и составления её алгоритма, бывает очень трудно представить себе собственно процесс работы программы. Для преодоления этих трудностей используют графическое представление алгоритма – блок-схему. В ней отдельные этапы работы представляются как геометрические фигуры с прослеженными путями действия. Вот пример такой схемы:
1
2
нет да 3
4
5
1 – блок ввода данных, 2 – блок обработки данных, 3 – блок условия, 4 – блок обработки решений, 5 – блок вывода данных
№14. Алгоритмы линейной и разветвляющейся структур.
Алгоритм
может быть линейным
– процесс
обработки информации по единственному
пути,
рассмотрим линейный алгоритм на примере
нахождения суммы 2х слагаемых:
или
ветвящимся,
в котором информация может двигаться
по разным путям в зависимости от условий,
рассмотрим на примере нахождения корней
уравнения:
15. Алгоритмы циклических структур: с предусловием, с постусловием и блоком модификации.
Цикл – повторяющаяся некоторое количество раз структурная единица программы.
Циклы бывают 3-х видов:
while ... do (с предусловием),
repeat ... until (с постусловием),
for ... to ... do (с параметром).
Циклы с предусловием означают, что есть условие, которое проверяется перед прохождением этапа цикла. Таких циклов два:
цикл, который повторяется определённое число раз,
цикл, который повторяется до тех пор, пока не выполнится условие.
Это циклы, описываемые командами for ... to ... do и while ... do.
Пример:
for i:=0 to 14 do команда;
Этот цикл повторит выполнение команды 15 раз.
Цикл же while <условие1> do команда; будет выполняться до тех пор, пока <условие1> будет истинным.
В отличие от них, цикл repeat ... until всегда выполнится хотя бы один раз, потому что это цикл с постусловием – он проверяет истинность некоторого условия в конце иттерации.
Пример:
repeat
команда;
until <условие1>
будет выполняться до тех пор, пока <условие1> будет ложным.
Помимо циклов, существует необходимость объединения команд в блоки. Объединяя команды таким образом, получают сложные операторы. Пример сложного оператора:
begin
команда1;
команда2;
команда3;
end;