Структуры данных и алгоритмы (1021739), страница 8
Текст из файла (страница 8)
Например, есть алгоритмы, которые работают значительно быстрее, если длина входных данных является простым числом, а не (к примеру) четным числом. В этом случае невозможно получить хорошую нижнюю границу времени выполнения,справедливую для всех л > по.30ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВтого же сочетания компилятор-компьютер. Предположим, что можно использовать1 000 секунд (примерно 17 минут) машинного времени для решения задачи.
Какоймаксимальный размер задачи, решаемой за это время? За 10 секунд каждый из четырех алгоритмов может решить задачи примерно одинакового размера, как показано во втором столбце табл. 1.3.Предположим, что получен новый компьютер (без дополнительных финансовыхзатрат), работающий в десять раз быстрее. Теперь за ту же цену можно использо43вать 10 секунд машинного времени — ранее 10 секунд.
Максимальный размерзадачи, которую может решить за это время каждая из четырех программ, показанв третьем столбце табл. 1.3. Отношения значений третьего и второго столбцов приведены в четвертом столбце этой таблицы. Здесь мы видим, что увеличение скорости компьютера на 1 000% приводит к увеличению только на 30% размера задачи,решаемой с помощью программы с временем выполнения О(2").
Таким образом,10-кратное увеличение производительности компьютера дает в процентном отношении значительно меньший эффект увеличения размера решаемой задачи. В действительности, независимо от быстродействия компьютера, программа с временемвыполнения О(2") может решать только очень небольшие задачи.Т(п)300020001000Рис. 1.6. Функции времени выполнения четырех программТаблица 1.3. Эффект от 10-кратного увеличения быстродействия компьютераВремявыполнения Tfn)Максимальный размерзадачи для 103 секундЮОпМаксимальный размерУвеличениезадачи для 104 секунд максимального размеразадачи1010010.0г14453.2п /212272.310131.3Ьп3я21.4. ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММ31Из третьего столбца табл. 1.3 ясно видно преимущество программ с временем выполнения О(п): 10-кратное увеличение размера решаемой задачи при 10-кратномувеличении производительности компьютера.
Программы с временем выполнения32О(л ) и О(л ) при увеличении быстродействия компьютера на 1 000% дают увеличение размера задачи соответственно на 230% и 320%. Эти соотношения сохранятся ипри дальнейшем увеличении производительности компьютера. DПоскольку существует необходимость решения задач все более увеличивающегосяразмера, мы приходим к почти парадоксальному выводу. Так как машинное времявсе время дешевеет, а компьютеры становятся более быстродействующими, мы надеемся, что сможем решать все большие по размеру и более сложные задачи.
Но вместес тем возрастает значимость разработки и использования эффективных алгоритмовименно с низкой степенью роста функции времени выполнения.Немного солиМы хотим еще раз подчеркнуть, что степень роста наихудшего времени выполнения — не единственный или самый важный критерий оценки алгоритмов и программ. Приведем несколько соображений, позволяющих посмотреть на критерийвремени выполнения с других точек зрения.1.2.3.4.5.Если создаваемая программа будет использована только несколько раз, тогдастоимость написания и отладки программы будет доминировать в общей стоимости программы, т.е. фактическое время выполнения не окажет существенноговлияния на общую стоимость.
В этом случае следует предпочесть алгоритм, наиболее простой для реализации.Если программа будет работать только с "малыми" входными данными, то степень роста времени выполнения будет иметь меньшее значение, чем константа,присутствующая в формуле времени выполнения. Вместе с тем и понятие"малости" входных данных зависит от точного времени выполнения конкурирующих алгоритмов. Существуют алгоритмы, такие как алгоритм целочисленного умножения (см. [96]), асимптотически самые эффективные, но которые никогда не используют на практике даже для больших задач, так как их константыпропорциональности значительно превосходят подобные константы других, болеепростых и менее "эффективных" алгоритмов.Эффективные, но сложные алгоритмы могут быть нежелательными, если готовыепрограммы будут поддерживать лица, не участвующие в написании этих программ.
Будем надеяться, что принципиальные моменты технологии созданияэффективных алгоритмов широко известны, и достаточно сложные алгоритмысвободно применяются на практике. Однако необходимо предусмотреть возможность того, что эффективные, но "хитрые" алгоритмы не будут востребованы изза их сложности и трудностей, -возникающих при попытке в них разобраться.Известно несколько примеров, когда эффективные алгоритмы требуют такихбольших объемов машинной памяти (без возможности использования более медленных внешних средств хранения), что этот фактор сводит на нет преимущество"эффективности" алгоритма.В численных алгоритмах точность и устойчивость алгоритмов не менее важны,чем их временная эффективность.1.5.
Вычисление времени выполнения программТеоретическое нахождение времени выполнения программ (даже без определенияконстант пропорциональности) — сложная математическая задача. Однако на практике определение времени выполнения (также без нахождения значения констант)является вполне разрешимой задачей — для этого нужно знать только несколько базовых принципов. Но прежде чем представить эти принципы, рассмотрим, как выполняются операции сложения и умножения с использованием О-символики.32ГЛАВА 1. ПОСТРОЕНИЕ И АНАЛИЗ АЛГОРИТМОВПусть Ti(n) и Т2(п) — время выполнения двух программных фрагментов Р1 и Р2,Tt(n) имеет степень роста О(/(л)), а Т2(п) — O(g(n)).
Тогда Т^п) + Т2(п), т.е. времяпоследовательного выполнения фрагментов Р1 и Р2, имеет степень ростаО(тах(/(л), g(n))). Для доказательства этого вспомним, что существуют константыci, c2, HI и п 2 такие, что при п > nl выполняется неравенство Tt(n) < Cif(n), и, аналогично, Т2(п) < c2g(n), если п > п2. Пусть л0 = тах(л!, п2). Если п > п0, то, очевидно, что Ti(n) + Т2(п) < Cif(n) + c2g(ri). Отсюда вытекает, что при п > п0 справедливо неравенство Тг(п) + Т2(п) < (сг + с2)тах(/(л), g(n)).
Последнее неравенство и означает, что Тг(п) + Т2(п) имеет порядок роста О(тах(/(л), g(ri))).Пример 1.8. Правило сумм, данное выше, используется для вычисления временипоследовательного выполнения программных фрагментов с циклами и ветвлениями.Пусть есть три фрагмента с временами выполнения соответственно О(п2), . О(л3) иО(п logn).
Тогда время последовательного выполнения первых двух фрагментов имеет порядок O(max(n2, л3)), т.е. О(п3). Время выполнения всех трех фрагментов имеетпорядок О(тах(л3, п logn)), это то же самое, что О(л3). ПВ общем случае время выполнения конечной последовательности программныхфрагментов, без учета констант, имеет порядок фрагмента с наибольшим временем выполнения. Иногда возможна ситуация, когда порядки роста времен нескольких фрагментов несоизмеримы (ни один из них не больше, чем другой, но они и не равны). Дляпримера рассмотрим два фрагмента с временем выполнения О(/(л)) и O(g(n)), гдеп 4 , если л четное;л 2 , если л нечетное,•, ,[л2, если л четное;[ л , если л нечетное.В данном случае правило сумм можно применить непосредственно и получить времявыполнения O(max(/r(n), g(n)), т.е.
л4 при п четном и л3, если п нечетно.Из правила сумм также следует, что если g(n) < f(n) для всех л, превышающихл0, то выражение О(/(л) + g(n)) эквивалентно О(/(л)). Например, О(л2 + л) то же самое, что О(л2).Правило произведений заключается в следующем. Если Т±(п) и Т2(п) имеют степени роста О(/(л)) и O(g(n)) соответственно, то произведение Т1(п)Т2(п) имеет степеньроста О(/(л)£(л)). Читатель может самостоятельно доказать это утверждение, используя тот же подход, который применялся при доказательстве правила сумм. Из правила произведений следует, что О(с/(л)) эквивалентно O(f(n)), если с — положительная константа.
Например, О(л2/2) эквивалентно О(п2).Прежде чем переходить к общим правилам анализа времени выполнения программ, рассмотрим простой пример, иллюстрирующий процесс определения временивыполнения.Пример 1.9. Рассмотрим программу сортировки bubble (пузырек), которая упорядочивает массив целых чисел в возрастающем порядке методом "пузырька" (листинг1.4). За каждый проход внутреннего цикла (операторы (3)-(6)) "пузырек" с наименьшим элементом "всплывает" в начало массива.Листинг 1 .4. Сортировка методом „пузырька"' .
' . ' • ' •.••• ' ' • . " •• : ' • . " . : . ' . .•,.-.'••procedure bubble ( var A: array [1..л] of integer );{ Процедура упорядочивает массив А в возрастающем порядке }vari, j, temp: integer;begin(1)for i:= 1 to n - 1 do(2)for j:= n down to i + 1 do(3)if A[j - 1] > A[j] then begin{ перестановка местами A[j-l] и A[j] }(4)temp-.= A[j - 1] ;1.5. ВЫЧИСЛЕНИЕ ВРЕМЕНИ ВЫПОЛНЕНИЯ ПРОГРАММ33Alj - 1]:= A [ j ] ;A ( j ] : = temp;(5)(6)endend; { bubble }Число элементов п, подлежащих сортировке, может служить мерой объема входных данных.
Сначала отметим, что все операторы присваивания имеют некотороепостоянное время выполнения, независящее от размера входных данных. Таким образом, операторы (4) - (6) имеют время выполнения порядка О(1). Запись О(1) означает "равнозначно некой константе". В соответствии с правилом сумм время выполнения этой группы операторов равно О(тах(1, 1, 1)) = О(1).Теперь мы должны подсчитать время выполнения условных и циклических операторов.
Операторы if и for вложены друг в друга, поэтому мы пойдем от внутреннихоператоров к внешним, последовательно определяя время выполнения условного оператора и каждой итерации цикла. Для оператора if проверка логического выражениязанимает время порядка О(1). Мы не знаем, будут ли выполняться операторы в телеусловного оператора (строки (4) - (6)), но поскольку мы ищем наихудшее время выполнения, то, естественно, предполагаем, что они выполняются.
Таким образом, получаем, что время выполнения группы операторов (3) - (6) имеет порядок О(1).Далее рассмотрим группу (2) - (6) операторов внутреннего цикла. Общее правиловычисления времени выполнения цикла заключается в суммировании времени выполнения каждой итерации цикла. Для операторов (2) - (6) время выполнения накаждой итерации имеет порядок О(1). Цикл выполняется п - i раз, поэтому по правилу произведений общее время выполнения цикла имеет порядок О((п - i) x 1), чторавно О(п - i).Теперь перейдем к внешнему циклу, который содержит все исполняемые операторы программы. Оператор (1) выполняется п - 1 раз, поэтому суммарное время выполнения программы ограничено сверху выражениемкоторое имеет порядок О(п2).
Таким образом, программа "пузырька" выполняется завремя, пропорциональное квадрату числа элементов, подлежащих упорядочиванию. Вглаве 8 мы рассмотрим программы с временем выполнения порядка О(п logn), котороесущественно меньше О(и2), поскольку при больших п logn1 значительно меньше п. ППеред формулировкой общих правил анализа программ позвольте напомнить, что нахождение точной верхней границы времени выполнения программ только в редких случаях так же просто, как в приведенном выше примере, в общем случае эта задача является интеллектуальным вызовом исследователю.
Поэтому не существует исчерпывающегомножества правил анализа программ. Мы можем дать только некоторые советы и проиллюстрировать их с разных точек зрения примерами, приведенными в этой книге.Теперь дадим несколько правил анализа программ. В общем случае время выполнения оператора или группы операторов можно параметризовать с помощью размеравходных данных и/или одной или нескольких переменных.
Но для времени выполнения программы в целом допустимым параметром может быть только п, размервходных данных.1.Время выполнения операторов присваивания, чтения и записи обычно имеет порядок О(1). Есть несколько исключений из этого правила, например в языкеPL/1, где можно присваивать большие массивы, или в любых других языках,допускающих вызовы функций в операторах присваивания.Время выполнения последовательности операторов определяется с помощью правила сумм. Поэтому степень роста времени выполнения последовательности опе-2.1Если не указано другое, то будем считать, что все логарифмы определены по основанию 2.Однако отметим, что выражение O(logn) не зависит от основания логарифма, посколькуlogon = clog(,n, где с = logab.34ГЛАВА 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
