Читайте также:
|
На всех этапах разработки программ необходимо анализированть их характеристики, к которым прежде всего относятся надежность и эффективность. Надежность программ тесно связана с их формальной корректностью.
На практике для анализа и обеспечения корректности проводят верификацию (доказательство правильности) и ручное тестирование (проверочное исполнение) наиболее важных и сложных частей разрабатываемого алгоритма.
Верификация включает доказательство конечности процесса исполнения и правильности результата алгоритма. Обычно используется метод математической индукции.
В некоторых случаях для пояснения и обоснования алгоритма в учебнике приводится инвариант цикла - утверждение, соблюдаемое при каждом попадании управления в некоторую точку цикла. Формулирование инварианта цикла - наиболее трудная часть доказательства, проверить его правильность гораздо легче. Инвариант цикла выражает основную идею его построения и его удобно записывать в виде комментария в соответствующем месте цикла.
Чаще всего для пояснения работы алгоритма в учебнике приводится трассировочная таблица его тестирования. Ручное тестирование алгоритма с составлением трассировочных таблиц играет важную роль при разработке и анализе программ и хорошо развивает алгоритмическое мышление программистов.
Эффективность программы определяется временем работы алгоритма и объемом памяти для алгоритма и данных. Важную роль в программировании играет пространственно-временная закономерность: уменьшение времени работы алгоритма приводит, как правило, к дополнительным затратам памяти и, наоборот, экономия памяти обычно приводит к замедлению работы программы. Таким образом, эти два параметра программы тесно взаимосвязаны. Изменяя один из них, можно в определенной степени управлять значением другого.
Под сложностью алгоритма в литературе обычно имеют в виду не трудность его разработки или понимания, а его вычислительную сложность, т.е. время и объем памяти, необходимые для решения задачи. В книге приводятся оценки сложности ряда алгоритмов и методов решения задач. Сложность алгоритма обычно оценивается асимптотически - по скорости роста необходимого времени и памяти при возрастании размера задачи.
Размер задачи n определяется количеством обрабатываемых данных: длиной входной последовательности, размером матриц, числом вершин или ребер графа и т. д. Время измеряется количеством основных элементарных операций, необходимых для решения задачи (пересылка, сложение, сравнение и т. п.).
Для сравнения скорости роста функций в литературе используются различные обозначения. Рассмотрим некоторые из них – так называемое О-обозначение, W-обозначение и Q-обозначение [21, 35].
Выражение f(n) = O( g(n) ) читается "f(n) есть о большое от g(n)" (говорят также “f(n) имеет значение порядка g(n)”) и обозначает, что g(n) является верхней границей для f(n), то есть f(n) £ C×g(n) для некоторой константы C.
Выражение f(n) = W(g(n))читается "f(n) есть омега большое от g(n)" и обозначает, что g(n) может служить нижней границей для f(n).
Выражение f(n) = Q(g(n))читается "f(n) есть тета большое от g(n)" и обозначает, что g(n) является асимптотически точной оценкой для f(n).
Справедливы отношения: f(n) = W(g(n)) <==> g(n) = O(f(n)),
f(n) = Q(g(n)) ==> g(n) = Q(f(n)), f(n)=Q(g(n)) <==> f(n)=O(g(n)) и g(n)=O(f(n)).
Примеры: n5+6*n = O(n5), величина порядка О(1) не зависит от n (т. е. является константой).
Таким образом, утверждение, что время или память имеет значение порядка f(n) или О(f(n)) означает, что при увеличении размера задачи n эта величина не превышает C· f(n), C = const >0.
Дата добавления: 2015-01-12; просмотров: 37 | Поможем написать вашу работу | Нарушение авторских прав |