Файл: Программная инженерия, 18. 04. 2013. Красноярск сфу 2013 2.pdf

24 и P
2
, имеет степень роста ах, g(n))). Для доказательства этого вспомним, что существуют константы c
1
, c
2
, n
1
и n
2
такие, что при п ≥ выполняется неравенство T
1
(n) ≤ c
1
f(n), и, аналогично, T
2
(n) ≤ c
2
g(n), если п ≥ n
2
. Пусть n
0
= max(n
1
, n
2
). Если п ≥ n
0
, то, очевидно, что T
1
(n) + T
2
(n)≤
≤ c
1
f(n) + c
2
g(n). Отсюда вытекает, что при п ≥ n
0 справедливо неравенство
T
1
(n) + T
2
(n)≤ (c
1
+ c
2
) max(f(n), g(n)). Последнее неравенство и означает, что T
1
(n) + имеет порядок роста O(max(f(n), g(n))). Правило сумм, данное выше, используется для вычисления времени последовательного выполнения программных фрагментов с циклами и ветвлениями. Предположим, что есть три фрагмента с временами выполнения соответственно п пи п log n). Тогда время последовательного выполнения первых двух фрагментов имеет порядок O(max(n
2
, п, те. п. Время выполнения всех трех фрагментов имеет порядок
O(max(n
3
, п log n)), это тоже самое, что O(n
3
). В общем случае время выполнения конечной последовательности программных фрагментов, без учета констант, имеет порядок фрагмента с наибольшим временем выполнения. Иногда возможна ситуация, когда порядки роста времен нескольких фрагментов несоизмеримы (ни один из них не больше, чем другой, но они и неравны. Для примера рассмотрим два фрагмента с временем выполнения O(f(n)) и O(g(n)), где
n
4
, если n четное
f(n) =
n
2
, если n нечетное,
n
2
, если n четное
g(n) =
n
3
, если n нечетное. В данном случае правило сумм можно применить непосредственно и получить время выполнения O(max(f(n), g(n)), те при n четном и n
3
, если нечетно. Из правила сумм также следует, что если g(n)≤ f(n) для всех п превышающих, то выражение O(f(n) + g(n)) эквивалентно O(f(n)). Например, п + п) тоже самое, что п. Правило произведений заключается в следующем. Если T
1
(n) и T
2
(n) имеют степени роста O(f(n)) и O(g(n)) соответственно, то произведение
T
1
(n) x T
2
(n) имеет степень роста O(f(n) x g(n)). Из правила произведений следует, что O(cf(n)) эквивалентно O(f(n)), если с – положительная константа. Например, O(n
2
/ 2) эквивалентно O(n
2
). Прежде чем переходить к общим правилам анализа времени выполнения программ, рассмотрим простой пример, иллюстрирующий процесс определения времени выполнения.

25 Рассмотрим программу сортировки bubble (пузырек, которая упорядочивает массив целых чисел в возрастающем порядке методом пузырька. За каждый проход внутреннего цикла (операторы (3)–(6)) пузырек с наименьшим элементом всплывает в начало массива.
procedure bubble (var A: array[1..n] of integer);
Процедура упорядочивает массив A в возрастающем порядке
var
i, j, temp: integer;
begin
(1) for i:= 1 to n – 1 do
(2) for j:= n downto i + 1 do
(3) if A[j – 1] > A[j] then begin
перестановка местами A[j – 1] и A[j]}
(4) temp := A[j – 1] ;
(5) A[j – 1] := A[j];
(6) A[j] := temp;
end
end; Число элементов п, подлежащих сортировке, может служить мерой объема входных данных. Сначала отметим, что все операторы присваивания имеют некоторое постоянное время выполнения, независящее от размера входных данных. Таким образом, операторы (4) – (6) имеют время выполнения порядка O(1). Запись O(1) означает равнозначно некой константе. В соответствии с правилом сумм время выполнения этой группы операторов равно ах, 1, 1)) = O(1). Теперь необходимо подсчитать время выполнения условных и циклических операторов. Операторы и for вложены друг в друга, поэтому мы пойдем от внутренних операторов к внешним, последовательно определяя время выполнения условного оператора и каждой итерации цикла. Для оператора проверка логического выражения занимает время порядка
O(1). Мы не знаем, будут ли выполняться операторы в теле условного оператора (строки (4) – (6)), но поскольку мы ищем наихудшее время выполнения, то, естественно, предполагаем, что они выполняются. Таким образом, получаем, что время выполнения группы операторов (3) – (6) имеет порядок O(1). Далее рассмотрим группу (2) – (6) операторов внутреннего цикла. Общее правило вычисления времени выполнения цикла заключается в суммировании времени выполнения каждой итерации цикла. Для операторов) время выполнения на каждой итерации имеет порядок O(1).

26 Цикл выполняется п – i раз, поэтому по правилу произведений общее время выполнения цикла имеет порядок O((n – i) х 1), что равно O(n – i). Теперь перейдем к внешнему циклу, который содержит все исполняемые операторы программы. Оператор (1) выполняется п – 1 раз, поэтому суммарное время выполнения программы ограничено сверху выражением, которое имеет порядок п. Таким образом, программа пузырька выполняется за время, пропорциональное квадрату числа элементов, подлежащих упорядочиванию. В главе 3 будут рассмотрены программы с временем выполнения порядка п log n), которое существенно меньше п, поскольку при больших п log n
1
значительно меньше п Перед формулировкой общих правил анализа программ позвольте напомнить, что нахождение точной верхней границы времени выполнения программ только в редких случаях также просто, как в приведенном выше примере, в общем случае эта задача является интеллектуальным вызовом исследователю. Поэтому не существует исчерпывающего множества правил анализа программ. Можно дать только некоторые советы и проиллюстрировать их с разных точек зрения примерами, приведенными в этом пособии. Дадим несколько правил анализа программ. В общем случае время выполнения оператора или группы операторов можно параметризовать с помощью размера входных данных и/или одной или нескольких переменных. Но для времени выполнения программы в целом допустимым параметром может быть только п, размер входных данных.
1. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок O(1). Есть несколько исключений из этого правила, например в языке PL / 1, где можно присваивать большие массивы, или в любых других языках, допускающих вызовы функций в операторах присваивания. Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности операторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности Если не указано другое, то будем считать, что все логарифмы определены по основанию. Однако отметим, что выражение O(log n) не зависит от основания логарифма, поскольку log
a
n = c log
b
n, где с = log
a
b.

27 3. Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок O(1). Время для всей конструкции состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь.
4. Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок O(1)). Часто время выполнения цикла вычисляется, пренебрегая определением констант пропорциональности, как произведение количества выполненных итераций цикла на наибольшее возможное время выполнения операторов тела цикла. Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно. Вызовы процедур Для программ, содержащих несколько процедур (среди которых нет рекурсивных, можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная стой, которая не имеет вызовов других процедур. (Вызов процедур определяем по наличию оператора call.) Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы. Если есть рекурсивные процедуры, то нельзя упорядочить все процедуры таким образом, чтобы каждая процедура вызывала только процедуры, время выполнения которых подсчитано на предыдущем шаге. В этом случае мы должны с каждой рекурсивной процедурой связать временную функцию Т(п), где n определяет объем аргументов процедуры. Затем необходимо получить рекуррентное соотношение для Т(п), те. уравнение (или неравенство) для Т(п), где участвуют значения T(k) для различных значений. Техника решения рекуррентных соотношений зависит от вида этих соотношений. Проанализируем простую рекурсивную программу. Ниже представлен листинг программы вычисления факториала n!, те. вычисления произведения целых чисел от 1 до n включительно.

28
function fact (n: integer): integer;
{ fact(n) вычисляет п }
begin
(1) if n <= 1 then
(2) fact := 1
else
(3) fact := n * fact(n – 1)
end; Естественной мерой объема входных данных для функции fact является значение n. Обозначим через Т(п) время выполнения программы. Время выполнения для строки) имеет порядок O(1), а для строки (3)
– O(1) + Т(п – 1). Таким образом, для некоторых констант си имеем
c + Т(п – 1), если n > 1;
T(n) = (1.1)
d, если n ≤ 1. Полагая, что пи раскрывая в соответствии с соотношением (1.1) выражение Т(п – 1) (те. подставляя в (1.1) п – 1 вместо п, получим
Т(п) = с + Т(п – Аналогично, если п > 3, раскрывая Т(п – 2), получим
Т(п) = с + Т(п – 3). Продолжая этот процесс, в общем случае для некоторого п > i, имеем Т(п) = ic + Т(п – i). Положив в последнем выражении
i = п – 1, окончательно получаем
Т(п) = с(п – 1) + T(1) = с(п – 1) + d. (1.2) Из (1.2) следует, что Т(п) имеет порядок п. Отметим, что в этом примере анализа программы мы предполагали, что операция перемножения двух целых чисел имеет порядок O(1). На практике, однако, программу, представленную выше, нельзя использовать для вычисления факториала при больших значений п, так как размер получаемых в процессе вычисления целых чисел может превышать длину машинного слова. Общий метод решения рекуррентных соотношений, подобных соотношению из рассмотренного примера, состоит в последовательном раскрытии выражений T(k) в правой части уравнения (путем подстановки в исходное соотношение k вместо п) до тех пор, пока не получится формула, у которой в правой части отсутствует Т (как в формуле (1.2)). При этом часто приходится находить суммы различных последовательностей. Если значения таких сумм нельзя вычислить точно, то для сумм находятся верхние границы, что позволяет, в свою очередь, получить верхние границы для Т(п).

29 Программы с операторами безусловного перехода При анализе времени выполнения программ мы неявно предполагали, что все ветвления входе выполнения процедур осуществлялись с помощью условных операторов и операторов циклов. Мы останавливаемся на этом факте, так как определяли время выполнения больших групп операторов путем применения правила сумм к этим группам. Однако операторы безусловного перехода (такие как goto) могут порождать более сложную логическую групповую структуру. В принципе операторы безусловного перехода можно исключить из программы. Но, к сожалению, язык Pascal не имеет операторов досрочного прекращения циклов, поэтому операторы перехода по необходимости часто используются в подобных ситуациях. Предлагается следующий подход для работы с операторами безусловного перехода, выполняющих выход из циклов, который гарантирует отслеживание всего цикла. Поскольку досрочный выход из цикла, скорее всего, осуществляется после выполнения какого-нибудь логического условия, то можно предположить, что это условие никогда не выполняется. Но этот консервативный подход никогда не позволит уменьшить время выполнения программы, так как мы предполагаем полное выполнение цикла. Для программ, где досрочный выход из цикла не исключение, а правило, консервативный подход значительно переоценивает степень роста времени выполнения в наихудшем случае. Если же переход осуществляется к ранее выполненным операторам, тов этом случае вообще нельзя игнорировать оператор безусловного перехода, поскольку такой оператор создает петлю в выполнении программы, что приводит к нарастанию времени выполнения всей программы. Тем не менее анализ времени выполнения программ, использующих операторы безусловного перехода, создающих петли, возможен. Если программные петли имеют простую структуру, те. о любой паре петель можно сказать, что они или не имеют общих элементов, или одна петля вложена в другую, тов этом случае можно применить методы анализа времени выполнения, описанные в данном разделе. Анализ программ на псевдоязыке Если известна степень роста времени выполнения операторов, записанных с помощью неформального человеческого языкато, следовательно, можно проанализировать программу на псевдоязыке (такие программы будем называть псевдопрограммами). Однако часто невозможно в принципе знать время выполнения той части псевдопрограммы, которая еще не полностью реализована в формальных операторах языка программирования. Например, если в псевдопрограмме имеется неформальная часть, оперирующая абстрактными типами данных, то общее время выполнение программы в значительной степени зависит от способа реализации АТД. Это не является недостатком псевдопрограмм, так как одной из причин написания программ в терминах АТД является возможность выбора реализации АТД, в том числе по критерию времени выполнения. При анализе псевдопрограмм, содержащих операторы языка программирования и вызовы процедур, имеющих неформализованные фрагменты (такие как операторы для работы с АТД), можно рассматривать общее время выполнения программы как функцию пока неопределенного времени выполнения таких процедур. Время выполнения этих процедур можно параметризовать с помощью размера их аргументов. Часто выбранная математическая модель АТД сама подсказывает логически обоснованный размер аргументов. Например, если АТД строится на основе множеств, то часто количество элементов множества можно принять за параметр функции времени выполнения. В завершении данной главы опишем в общем виде процесс создания программы на языке программирования, например на языке Pascal. На рис. 1.2 схематически представлен процесс программирования. На первом этапе создается модель исходной задачи, для чего привлекаются соответствующие подходящие математические модели (например, теория графов) [1]. На этом этапе для нахождения решения также строится неформальный алгоритм. Математическая модель Абстрактные типы данных Структуры данных Неформальный алгоритм Программа на псевдоязыке Программа на языке Pascal Рис. 1.2. Функции времени выполнения четырех программ Наследующем этапе алгоритм записывается на псевдоязыке – смеси конструкций языка Pascal и менее формальных и обобщенных операторов на простом человеческом языке. Продолжением этого этапа является замена неформальных операторов последовательностью более детальных и формальных операторов. С этой точки зрения программа на псевдоязыке должна быть достаточно подробной, так как в ней фиксируются (определяются) различные типы данных, над которыми выполняются операторы. Затем создаются абстрактные типы данных для каждого зафиксированного типа данных (за исключением элементарных типов данных, таких как целые и действительные числа или символьные строки) путем задания имен процедурам для каждого оператора, выполняемого над данными абстрактного типа, и замены операторов вызовом соответствующих процедур. Третий этап процесса программирования обеспечивает реализацию каждого абстрактного типа данных и создание процедур для выполнения

31 различных операторов над данными этих типов. На этом этапе также заменяются все неформальные операторы псевдоязыка на код языка Pascal. Результатом этого этапа должна быть выполняемая программа. После ее отладки получается работающую программу. Предполагается что, используя пошаговый подход при разработке программ, схема которого показана на рис. 1.2, процесс отладки конечной программы будет небольшими безболезненным. Контрольные задания
1. Рассмотрим следующие функции от n:
f
1
(n) = n
2
;
f
2
(n) = n
2
+ 1000n;
n, если n нечетно,
f
3
(n) =
n
3
, если n четно
n, если n ≤ 100,
f
4
(n) =
n
3
, если n > 100. Укажите для каждой пары функций, когда f
i
(n) имеет порядок O(f
i
(n)) и когда f
i
(n) есть
(f
i
(n)).
2. Рассмотрим следующие функции от n:
n
2
для четных n ≥ 0,
g
1
(n) =
n
3
для нечетных n ≥ 1;
n для 0 ≤ n ≤ 100,
g
2
(n) =
n
3
для n > 100;
g
3
(n) = Укажите для каждой пары функций, когда g
i
(n) имеет порядок
O(g
i
(n)) и когда g
i
(n) есть
(g
i
(n)).
3. Предположим, что T
1
(n) есть
(f(n)) и T
2
(n) –
(g(n)). Какие из следующих выражений истины а) T
1
(n) + T
2
(n) =
(max(f(n), g(n))); б) T
1
(n)T
2
(n) есть
(f(n), g(n)).
4. Докажите, что следующие утверждения истинны а) 17 имеет порядок Об имеет порядок О, в) max (n
3
, 10n
2
) имеет порядок О, г) есть O(n
k + 1
) и
(n
k + 1
) для целых k,

32 д) если p(x) – полином степени k с положительных старшим коэффициентом, то p(x) есть O(n
k
) и
(n
k
).
5. Расположите следующие функции в порядке степени роста а) n, б)
n , в)
log n, где, ж) n
log
2
n, з) (и) (3/2)
n
, к) 17.

33