yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->1.4. Время выполнения программ

Алгоритмы и структуры данных

1.4. Время выполнения программ

В процессе решения прикладных задач выбор подходящего алгоритма вызывает определенные трудности. В самом деле, на чем основывать свой выбор, если алгоритм должен удовлетворять следующим противоречащим друг другу требованиям.

1.    Быть простым для понимания, перевода в программный код и отладки.

2.    Эффективно использовать компьютерные ресурсы и выполняться по возможности быстро.

Если написанная программа должна выполняться только несколько раз, то первое требование наиболее важно. Стоимость рабочего времени программиста обычно значительно превышает стоимость машинного времени выполнении программы, поэтому стоимость программы оптимизируется по стоимости написания (а не выполнения) программы. Если мы имеем дело с задачей, решение которой требует значительных вычислительных затрат, то стоимость выполнения программы может превысить стоимость написания программы, особенно если программа должна выполняться многократно. Поэтому, с финансовой точки зрения, более предпочтительным может стать сложный комплексный алгоритм (в надежде, что результирующая программа будет выполняться существенно быстрее, чем более простая программа). Но и в этой ситуации разумнее сначала реализовать простой алгоритм, чтобы определить, как должна себя вести более сложная программа. При построении сложной программной системы желательно реализовать ее простой прототип, на котором можно провести необходимые измерения и смоделировать ее поведение в целом, прежде чем приступать к разработке окончательного варианта. Таким образом, программисты должны быть осведомлены не только о методах построения быстрых программ, но и знать, когда их следует применить (желательно с минимальными программистскими усилиями).

Измерение времени выполнения программ

На время выполнения программы влияют следующие факторы.

1.    Ввод исходной информации в программу.

2.    Качество скомпилированного кода исполняемой программы.

3.    Машинные инструкции (естественные и ускоряющие), используемые для выполнения программы.

4.    Временная сложность алгоритма соответствующей программы.

Поскольку время выполнения программы зависит от ввода исходных данных; его можно определить как функцию от исходных данных. Но зачастую время выполнения программы зависит не от самих исходных данных, а от их "размера". В этом отношении хорошим примером являются задачи сортировки, которые мы подробно рассмотрим в главе 8. В задачах сортировки в качестве входных данных выступает список элементов, подлежащих сортировке, а в качестве выходного результата — те же самые элементы, отсортированные в порядке возрастания или убывания. Например, входной список 2, 1, 3, 1, 5, 8 будет преобразован в выходной список 1, 1, 2, 3, 5, 8 (в данном случае список отсортирован в порядке возрастания). Естественной мерой объема входной информации для программы сортировки будет число элементов, подлежащих сортировке, или, другими словами, длина входного списка. В общем случае длина входных данных— подходящая мера объема входной информации, и если не будет оговорено иное, то в качестве меры объема входной информации мы далее будем понимать именно длину входных данных.

Обычно говорят, что время выполнения программы имеет порядок Т(n) от входных данных размера n. Например, некая программа имеет время выполнения Т(n) = сn2, где с — константа. Единица измерения Т(n) точно не определена, но мы будем понимать Т(n) как количество инструкций, выполняемых на идеализированном компьютере.

Для многих программ время выполнения действительно является функцией входных данных, а не их размера. В этой ситуации мы определяем Т(n) как время выполнения в наихудшем случае, т.е. как максимум времени выполнения по всем входным данным размера n. Мы также будем рассматривать Тср(n) как среднее (в статистическом смысле) время выполнения по всем входным данным размера n. Хотя Тср(n) является достаточно объективной мерой времени выполнения, но часто нельзя предполагать (или обосновать) равнозначность всех входных данных. На практике среднее время выполнения найти сложнее, чем наихудшее время выполнения, так как математически это трудноразрешимая задача и, кроме того, зачастую не имеет простого определения понятие "средних" входных данных. Поэтому в основном мы будем использовать наихудшее время выполнения как меру временной сложности алгоритмов, но не будем забывать и о среднем времени выполнения там, где это возможно.

Теперь сделаем замечание о втором и третьем факторах, влияющих на время выполнения программ: о компиляторе, используемом для компиляции программы, и машине, на которой выполняется программа. Эти факторы влияют на то, что для измерения времени выполнения Т(n) мы не можем применить стандартные единицы измерения, такие как секунды или миллисекунды. Поэтому мы можем только делать заключения, подобные "время выполнения такого-то алгоритма пропорционально n2". Константы пропорциональности также нельзя точно определить, поскольку они зависят от компилятора, компьютера и других факторов.

Асимптотические соотношения

Для описания скорости роста функций используется О-символика. Например, когда мы говорим, что время выполнения Т(n) некоторой программы имеет порядок О(n2) (читается "о-большое от n в квадрате" или просто "о от n в квадрате"), то подразумевается, что существуют положительные константы с и n0 такие, что для всех n, больших или равных n0, выполняется неравенство Т(n) ≤ сn2.

Пример 1.4. Предположим, что Т(0) = 1, Т(1) = 4 и в общем случае Т(n) = (n + 1)2. Тогда Т(n) имеет порядок О(n2): если положить n0 = 1 и с = 4, то легко показать, что для n ≥ 1 будет выполняться неравенство (n + 1)2 ≤ 4n2. Отметим, что нельзя положить n0 = О, так как T(0) = 1 и, следовательно, это значение при любой константе с больше с02= 0.

Подчеркнем: мы предполагаем, что все функции времени выполнения определены на множестве неотрицательных целых чисел и их значения также неотрицательны, но необязательно целые. Будем говорить, что Т(n) имеет порядок О(f(n)), если существуют константы с и n0 такие, что для всех n ≥ n0 выполняется неравенство Т(n) ≤ cf(n). Для программ, у которых время выполнения имеет порядок О(f(n)), говорят, что они имеют порядок (или степень) роста f(n).

Пример 1.5. Функция Т(n) = Зn3 + 2n2 имеет степень роста О(n3). Чтобы это показать, надо положить n0 = 0 и с = 5, так как легко видеть, что для всех целых n ≥ 0 выполняется неравенство Зn3 + 2n2 ≤ 5n3. Можно, конечно, сказать, что Т(n) имеет порядок О(n4), но это более слабое утверждение, чем то, что Т(n) имеет порядок роста О(n3).В качестве следующего примера докажем, что функция 3n не может иметь порядок О(2n). Предположим, что существуют константы с и п0 такие, что для всех п > nо выполняется неравенство 3n ≤ c2n. Тогда с ≥ (3/2)n для всех n ≥ n0. Но (3/2)n принимает любое, как угодно большое, значение при достаточно большом n, поэтому не существует такой константы с, которая могла бы мажорировать (3/2)n для всех п.

Когда мы говорим, что Т(п) имеет степень роста О(f(n)), то подразумевается, что f(n) является верхней границей скорости роста Т(п). Чтобы указать нижнюю границу скорости роста Т(п), используется обозначение: Т(п) есть Ω(g(n)) (читается "омега-большое от g(n)" или просто "омега от g(n)"), это подразумевает существование такой константы с, что бесконечно часто (для бесконечного числа значений n) выполняется неравенство Т(п) > cg(n). (Отметим асимметрию в определениях О- и Ω-символики. Такая асимметрия бывает полезной, когда алгоритм работает быстро на достаточно большом подмножестве, но не на всем множестве входных данных. Например, есть алгоритмы, которые работают значительно быстрее, если длина входных данных является простым числом, а не (к примеру) четным числом. В этом случае невозможно получить хорошую нижнюю границу времени выполнения, справедливую для всех п ≥ nо.)

Пример 1.6. Для проверки того, что Т(п) = n3 + 2п2 есть Ω(n3), достаточно положить с = 1. Тогда Т(п) ≥ сп3 для п = О, 1,... .

Для другого примера положим, что Т(п) = п для нечетных п ≥ 1 и Т(п) = n2/100 — для четных n ≥ О. Для доказательства того, что Т(п) есть Ω(n2), достаточно положить с = 1/100 и рассмотреть множество четных чисел n = 0, 2, 4, 6,... .

Ограниченность показателя степени роста

Итак, мы предполагаем, что программы можно оценить с помощью функций времени выполнения, пренебрегая при этом константами пропорциональности. С этой точки зрения программа с временем выполнения О(n2), например, лучше программы с временем выполнения О(п). Константы пропорциональности зависят не только от используемых компилятора и компьютера, но и от свойств самой программы. Пусть при определенной комбинации компилятор-компьютер одна программа выполняется за 100n2 миллисекунд, а вторая — за 5n3 миллисекунд. Может ли вторая программа быть предпочтительнее, чем первая?

Ответ на этот вопрос зависит от размера входных данных программ. При размере входных данных п < 20 программа с временем выполнения 5n3 завершится быстрее, чем программа с временем выполнения 100n2. Поэтому, если программы в основном выполняются с входными данными небольшого размера, предпочтение необходимо отдать программе с временем выполнения О(n3). Однако при возрастании n отношение времени выполнения 5n3/100n2 = n/20 также растет. Поэтому при больших n программа с временем выполнения О(n2) становится предпочтительнее программы с временем выполнения О(n3). Если даже при сравнительно небольших n, когда время выполнения обеих программ примерно одинаково, выбор лучшей программы представляет определенные затруднения, то естественно для большей надежности сделать выбор в пользу программы с меньшей степенью роста.

Другая причина, заставляющая отдавать предпочтение программам с наименьшей степенью роста времени выполнения, заключается в том, что чем меньше степень роста, тем больше размер задачи, которую можно решить на компьютере. Другими словами, если увеличивается скорость вычислений компьютера, то растет также и размер задач, решаемых на компьютере. Однако незначительное увеличение скорости вычислений компьютера приводит только к небольшому увеличению размера задач, решаемых в течение фиксированного промежутка времени, исключением из этого правила являются программы с низкой степенью роста, как О(n) и О(п logn).

Пример 1.7. На рис. 1.6 показаны функции времени выполнения (измеренные в секундах) для четырех программ с различной временной сложностью для одного и того же сочетания компилятор-компьютер. Предположим, что можно использовать 1 000 секунд (примерно 17 минут) машинного времени для решения задачи. Какой максимальный размер задачи, решаемой за это время? За 103 секунд каждый из четырех алгоритмов может решить задачи примерно одинакового размера, как показано во втором столбце табл. 1.3.

Предположим, что получен новый компьютер (без дополнительных финансовых затрат), работающий в десять раз быстрее. Теперь за ту же цену можно использовать 104 секунд машинного времени — ранее 103 секунд. Максимальный размер задачи, которую может решить за это время каждая из четырех программ, показан в третьем столбце табл. 1.3. Отношения значений третьего и второго столбцов приведены в четвертом столбце этой таблицы. Здесь мы видим, что увеличение скорости компьютера на 1 000% приводит к увеличению только на 30% размера задачи, решаемой с помощью программы с временем выполнения О(2n). Таким образом, 10-кратное увеличение производительности компьютера дает в процентном отношении значительно меньший эффект увеличения размера решаемой задачи. В действительности, независимо от быстродействия компьютера, программа с временем выполнения О(2n) может решать только очень небольшие задачи.

Время      выполнения Т(п)

Максимальный размер задачи для 103 секунд

Максимальный размер задачи для 104 секунд

Увеличение      максимального размера задачи

100n

5n2

n3/2

2n

10

14

12

10

100

45

27

13

10.0

3.2

2.3

1.3

Из третьего столбца табл. 1.3 ясно видно преимущество программ с временем выполнения О(п): 10-кратное увеличение размера решаемой задачи при 10-кратном увеличении производительности компьютера. Программы с временем выполнения О(n3) и О(п2) при увеличении быстродействия компьютера на 1 000% дают увеличение размера задачи соответственно на 230% и 320%. Эти соотношения сохранятся и при дальнейшем увеличении производительности компьютера.

Поскольку существует необходимость решения задач все более увеличивающегося размера, мы приходим к почти парадоксальному выводу. Так как машинное время все время дешевеет, а компьютеры становятся более быстродействующими, мы надеемся, что сможем решать все большие по размеру и более сложные задачи. Но вместе с тем возрастает значимость разработки и использования эффективных алгоритмов именно с низкой степенью роста функции времени выполнения.

 

Немного соли

 

Мы хотим еще раз подчеркнуть, что степень роста наихудшего времени выполнения — не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерий времени выполнения с других точек зрения.

1.    Если создаваемая программа будет использована только несколько раз, тогда стоимость написания и отладки программы будет доминировать в общей стоимости программы, т.е. фактическое время выполнения не окажет существенного влияния на общую стоимость. В этом случае следует предпочесть алгоритм, наиболее простой для реализации.

2.    Если программа будет работать только с "малыми" входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа, присутствующая в формуле времени выполнения. Вместе с тем и понятие "малости" входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения (см. [96]), асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константы пропорциональности значительно превосходят подобные константы других, более простых и менее "эффективных" алгоритмов.

3.    Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ. Будем надеяться, что принципиальные моменты технологии создания эффективных алгоритмов широко известны, и достаточно сложные алгоритмы свободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но "хитрые" алгоритмы не будут востребованы из-за их сложности и трудностей, возникающих при попытке в них разобраться.

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

5.    В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

 

1.5. Вычисление времени выполнения программ

Теоретическое нахождение времени выполнения программ (даже без определения констант пропорциональности) — сложная математическая задача. Однако на практике определение времени выполнения (также без нахождения значения констант) является вполне разрешимой задачей — для этого нужно знать только несколько базовых принципов. Но прежде чем представить эти принципы, рассмотрим, как выполняются операции сложения и умножения с использованием О-символики.

Пусть Т1(n) и T2(n) — время выполнения двух программных фрагментов Р1 и Р2, Т1(n) имеет степень роста О(f(n)), а Т2(n) — O(g(n)). Тогда Т1(n) + T2(n), т.е. время последовательного выполнения фрагментов Р1 и Р2, имеет степень роста О(mах(f(n), g(n))). Для доказательства этого вспомним, что существуют константы c1, с2, n1 и n2 такие, что при n ≥ n1 выполняется неравенство T1(n) ≤ c1f(n), и, аналогично, Т2(n) ≤ с2g(n), если n ≥ n2. Пусть no = mах(n1, n2). Если n > no, то, очевидно, что Т1(n) + Т2(n) ≤ c1f(n) + c2g(n). Отсюда вытекает, что при n ≥ nо справедливо неравенство Т1(n) + T2(n) ≤ (c1 + с2)mах(f(n), g(n)). Последнее неравенство и означает, что Т1(n) + T2(n) имеет порядок роста О(mах(f(n), g(n))).

Пример 1.8. Правило сумм, данное выше, используется для вычисления времени последовательного выполнения программных фрагментов с циклами и ветвлениями. Пусть есть три фрагмента с временами выполнения соответственно О(n2), О(n3) и О(n logn). Тогда время последовательного выполнения первых двух фрагментов имеет порядок О(mах(n2, n3)), т.е. О(n3). Время выполнения всех трех фрагментов имеет порядок О(mах(n3, n logn)), это то же самое, что О(n3).

В общем случае время выполнения конечной последовательности программных фрагментов, без учета констант, имеет порядок фрагмента с наибольшим временем выполнения. Иногда возможна ситуация, когда порядки роста времен нескольких фрагментов несоизмеримы (ни один из них не больше, чем другой, но они и не равны). Для примера рассмотрим два фрагмента с временем выполнения О(f(n)) и O(g(n)), где

 

                f(n)=     n4, если n четное;                                     

   n2, если n нечетное,                                         

              

                  g(n)=   n2, если n четное;

    n3 , если n нечетное.

 

В данном случае правило сумм можно применить непосредственно и получить время выполнения О(mах(f(n), g(n)), т.е. n4 при n четном и n3, если n нечетно.

Из правила сумм также следует, что если g(n) ≤ f(n) для всех n, превышающих n0, то выражение О(f(n) + g(n)) эквивалентно O(f(n)). Например, О(n2 + n) то же самое, что О(n2).

Правило произведений заключается в следующем. Если Т1(n) и Т2(n) имеют степени роста О(f(n)) и O(g(n)) соответственно, то произведение Т1(n)T2(n) имеет степень роста O(f(n)g(n)). Вы можете самостоятельно доказать это утверждение, используя тот же подход, который применялся при доказательстве правила сумм. Из правила произведений следует, что О(сf(n)) эквивалентно О(f(n)), если с — положительная константа. Например, О(n2/2) эквивалентно О(n2).

Прежде чем переходить к общим правилам анализа времени выполнения программ, рассмотрим простой пример, иллюстрирующий процесс определения времени выполнения.

Пример 1.9. Рассмотрим программу сортировки bubble: (пузырек), которая упорядочивает массив целых чисел в возрастающем порядке методом "пузырька" (листинг 1.4). За каждый проход внутреннего цикла (операторы (3)-(6)) "пузырек" с наименьшим элементом "всплывает" в начало массива.

Листинг 1. 4.

procedure bubble { var A: array [l..n] of integer );

{ Процедура упорядочивает массив Л в возрастающем порядке }

var

і, j, temp: integer;

begin

(1)         for i:=l to n-l do

(2)        for j:= n downto і + 1 do

(3)        if Alj - 1] > A[j] then begin

{ перестановка местами Alj-1] и A[j] }

(4)                                 temp:= A[j -1];

(5)                                 A[j -  1]: = A[j];

(6)                                 A[j] :=  temp;

 end

end;   { bubble }

Число элементов n, подлежащих сортировке, может служить мерой объема входных данных. Сначала отметим, что все операторы присваивания имеют некоторое постоянное время выполнения, независящее от размера входных данных. Таким образом, операторы (4) - (6) имеют время выполнения порядка О(1). Запись О(1) означает "равнозначно некой константе". В соответствии с правилом сумм время выполнения этой группы операторов равно О(max(1, 1, 1)) = О(1).

Теперь мы должны подсчитать время выполнения условных и циклических операторов. Операторы if и for вложены друг в друга, поэтому мы пойдем от внутренних операторов  к внешним, последовательно определяя время выполнения условного оператора и каждой итерации цикла. Для оператора if проверка логического выражения занимает время порядка О(1). Мы не знаем, будут ли выполняться операторы в теле условного оператора (строки (4) — (6)), но поскольку мы ищем наихудшее время выполнения, то, естественно, предполагаем, что они выполняются. Таким образом, получаем, что время выполнения группы операторов (3) — (6) имеет порядок О(1).

Далее рассмотрим группу (2) - (6) операторов внутреннего цикла. Общее правило вычисления времени, выполнения цикла заключается в суммировании времени выполнения каждой итерации цикла. Для операторов (2) - (6) время выполнения на каждой итерации имеет порядок О(1). Цикл выполняется п - і раз, поэтому по правилу произведений общее время выполнения цикла имеет порядок О((п - і) * 1), что равно О(п - і).

Теперь перейдем к внешнему циклу, который содержит все исполняемые операторы программы. Оператор (1) выполняется n - 1 раз, поэтому суммарное время выполнения программы ограничено сверху выражением

,

которое имеет порядок О(n2). Таким образом, программа "пузырька" выполняется за время, пропорциональное квадрату числа элементов, подлежащих упорядочиванию. В тeмe 8 мы рассмотрим программы с временем выполнения порядка О(п logn), которое существенна меньше О(п ), поскольку при больших n logn (eсли не указано другое, то будем считать, что все логарифмы определены по основанию 2. Однако отметим, что выражение O(logn) не зависит от основания логарифма, поскольку logan= clogbn, где с =:logab.) значительно меньше n.

Перед формулировкой общих правил анализа программ позвольте напомнить, что нахождение точной верхней границы времени выполнения программ только в редких случаях так же просто, как в приведенном выше примере, в общем случае эта задача является интеллектуальным вызовом исследователю. Поэтому не существует исчерпывающего множества правил анализа программ. Мы можем дать только некоторые советы и проиллюстрировать их с разных точек зрения примерами, приведенными в этой книге.

• Теперь дадим несколько правил анализа программ. В общем случае время выполнения оператора или группы операторов можно параметризовать с помощью размера входных данных и/или одной или нескольких переменных. Но для времени выполнения программы в целом допустимым параметром может быть только n, размер входных данных.

1.    Время выполнения операторов присваивания, чтения и записи обычно имеет порядок О(1). Есть несколько исключений из этого правила, например в языке PL/1, где можно присваивать большие массивы, или в любых других языках, допускающих вызовы функций в операторах присваивания.

2.    Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности операторов без определения констант пропорциональности совпадает с наибольшим временем выполнения оператора в данной последовательности.

3.    Время выполнения условных операторов состоит из времени выполнения условно исполняемых операторов и времени вычисления самого логического выражения. Время вычисления логического выражения обычно имеет порядок О(1). Время для всей конструкции if-then-else состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значении логического выражения true (истина) и при значении false (ложь).

4.    Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок О(1)). Часто время выполнения цикла вычисляется, пренебрегая определением констант пропорциональности, как произведение количества выполненных итераций цикла на наибольшее возможное время выполнения операторов тела цикла. Время выполнения каждого цикла, если в программе их несколько, должно определяться отдельно.

 

Вызовы процедур.

Для программ, содержащих несколько процедур (среди которых нет рекурсивных), можно подсчитать общее время выполнения программы путем последовательного нахождения времени выполнения процедур, начиная с той, которая не имеет вызовов других процедур. (Вызов процедур мы определяем по наличию оператора call.) Так как мы предположили, что все процедуры нерекурсивные, то должна существовать хотя бы одна процедура, не имеющая вызовов других процедур. Затем можно определить время выполнения процедур, вызывающих эту процедуру, используя уже вычисленное время выполнения вызываемой процедуры. Продолжая этот процесс, найдем время выполнения всех процедур и, наконец, время выполнения всей программы.

Если есть рекурсивные процедуры, то нельзя упорядочить все процедуры таким образом, чтобы каждая процедура вызывала только процедуры, время выполнения которых подсчитано на предыдущем шаге. В этом случае мы должны с каждой рекурсивной процедурой связать временную функцию Т(п), где п определяет объем аргументов процедуры. Затем мы должны получить рекуррентное соотношение для Т(п), т.е. уравнение (или неравенство) для Т(п), где участвуют значения T(k) для различных значений k.

Техника решения рекуррентных соотношений зависит от вида этих соотношений, некоторые приемы их решения будут показаны в теме 9. Сейчас же мы проанализируем простую рекурсивную программу.

Пример 1.10. В листинге 1.5 представлена программа вычисления факториала n!, т.е. вычисления произведения целых чисел от 1 до п включительно.

Листинг 1. 5.

function  fact   (  n:   integer  ) :   integer;

fact(n)   вычисляет n!   }

begin

(1)       if   n   <=   1   then                                              

(2)            fact:=   1                                         

else

(3)            fact:- n * fact(n - 1)

end;   {  fact }

Естественной мерой объема входных данных для функции fact является значение п. Обозначим через Т(п) время выполнения программы. Время выполнения для строк(1) и (2) имеет порядок О(1), а для строки (3) — О(1) + Т(п - 1). Таким образом, для некоторых констант c и d имеем

                                  T(n)=      c+ T(n-1),       если n>1,      

d,                    если n ≤ 1.                                                     (1.1)

Полагая, что п > 2, и раскрывая в соответствии с соотношением (1.1) выражение Т(п - 1) (т.е. подставляя в (1.1) п - 1 вместо n), получим Т(п) = 2с + Т(п - 2). Аналогично, если п > 3, раскрывая Т(п - 2), получим Т(п) - 3с + Т(п - 3). Продолжая этот процесс, в общем случае для некоторого і, п > і, имеем Т(п) = іс + Т(п - і). Положив в последнем выражении і = n - 1, окончательно получаем

Т(п) = с(п - 1) + T(1) = с(п - 1) + d,                                         (1.2)

Из (1.2) следует, что Т(п) имеет порядок О(п). Отметим, что в этом примере анализа программы мы предполагали, что операция перемножения двух целых чисел имеет порядок О(1). На практике, однако, программу, представленную в листинге 1.5, нельзя использовать для вычисления факториала при больших значений n, так как размер получаемых в процессе вычисления целых чисел может превышать длину машинного слова.

Общий метод решения рекуррентных соотношений, подобных соотношению из примера 1.10, состоит в последовательном раскрытии выражений T(k) в правой части уравнения (путем подстановки в исходное соотношение k вместо п) до тех пор, пока не получится формула, у которой в правой части отсутствует Т (как в формуле (1.2)). При этом часто приходится находить суммы различных последовательностей; если значения таких сумм нельзя вычислить точно, то для сумм находятся верхние границы, что позволяет, в свою очередь, получить верхние границы для Т(п).

 

Программы с операторами безусловного перехода

 

При анализе времени выполнения программ мы неявно предполагали, что все ветвления в ходе выполнения процедур осуществлялись с помощью условных операторов и операторов циклов. Мы останавливаемся на этом факте, так как определяли время выполнения больших групп операторов путем применения правила сумм к этом группам. Однако операторы безусловного перехода (такие как goto) могут порождать более сложную логическую групповую структуру. В принципе, операторы безусловного перехода можно исключить из программы. Но, к сожалению, язык Pascal не имеет операторов досрочного прекращения циклов, поэтому операторы перехода по необходимости часто используются в подобных ситуациях.

Мы предлагаем следующий подход для работы с операторами безусловного перехода, выполняющих выход из циклов, который гарантирует отслеживание всего цикла. Поскольку досрочный выход из цикла скорее всего осуществляется после выполнения какого-нибудь логического условия, то мы можем предположить, что это условие никогда не выполняется. Но этот консервативный подход никогда не позволит уменьшить время выполнения программы, так как мы предполагаем полное выполнение цикла. Для программ, где досрочный выход из цикла не исключение, а правило, консервативный подход значительно переоценивает степень роста времени выполнения в наихудшем случае. Бели же переход осуществляется к ранее выполненным операторам, то в этом случае вообще нельзя игнорировать оператор безусловного перехода, поскольку такой оператор создает петлю в выполнении программы, что приводит в нарастанию времени выполнения всей программы.

Нам не хотелось бы, чтобы у читателя сложилось мнение о невозможности анализа времени выполнения программ, использующих операторы безусловного перехода, создающих петли. Если программные петли имеют простую структуру, т.е. о любой паре петель можно сказать, что они или не имеют общих элементов, или одна петля вложена в другую, то в этом случае можно применить методы анализа времени выполнения, описанные в данном разделе. (Конечно, бремя ответственности за правильное определение структуры петли ложится на того, кто проводит анализ.) Мы без колебаний рекомендуем применять описанные методы для анализа программ, написанных на таких языках, как Fortran, где использование операторов безусловного перехода является естественным делом, но для анализируемых программ допустимы петли только простой структуры.

 

Анализ программ на псевдоязыке

Если мы знаем степень роста времени выполнения операторов, записанных с помощью неформального "человеческого" языка, то, следовательно; сможем проанализировать программу на псевдоязыке (такие программы будем называть псевдопрограммами). Однако часто мы не можем в принципе знать время выполнения той части псевдопрограммы, которая еще не полностью реализована в формальных операторах языка программирования. Например, если в псевдопрограмме имеется неформальная часть, оперирующая абстрактными типами данных, то общее время выполнение программы в значительной степени зависит от способа реализации ATД. Это не является недостатком псевдопрограмм, так как одной из причин написания программ в терминах АТД является возможность выбора реализации АТД, в том числе по критерию времени выполнения.

При анализе псевдопрограмм, содержащих операторы языка программирования и вызовы процедур, имеющих неформализованные фрагменты (такие как операторы для работы с АТД), можно рассматривать общее время выполнения программы как функцию пока не определенного времени выполнения таких процедур. Время выполнения этих процедур можно параметризовать с помощью "размера" их аргументов. Так же, как и "размер входных данных", "размер" аргументов — это предмет для обсуждения и дискуссий. Часто выбранная математическая модель АТД подсказывает логически обоснованный размер аргументов. Например, если АТД строится на основе множеств, то часто количество элементов множества можно принять за параметр функции времени выполнения. В последующих темах вы встретите много примеров анализа времени выполнения псевдопрограмм.

 

 

7