Главная Промышленная автоматика.

в качестве следующего примера докажем, что функция З" не может иметь порядок 0(2"). Предположим, что существуют константы с и По также, что для всех п > щ выполняется неравенство 3" < с2". Тогда с > (3/2)" для всех л > лр- Но (3/2)" принимает любое, как угодно болъщое, значение при достаточно больщом п, поэтому не существует такой константы с, которая могла бы мажорировать (3/2)" для всех п. П

Когда мы говорим, что Т{п) имеет степень роста О(Дге)), то подразумевается, что f(n) является верхней границей скорости роста Т(п). Чтобы указать нюкнюю границу скорости роста Т{п), используется обозначение: Т(п) есть Q(g(ra)) (читается "омега-больщое от g{n)" или просто "омега от g{n}"), это подразумевает существование такой константы с, что бесконечно част9 (для бесконечного числа значений п) выполняется неравенство Т(п) > cg{n)}

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

Для другого примера положим, что Т(п) = п для нечетныхга > 1 и Т{п) - п/100 - для четных « > 0. Для доказательства того, что Т(п.)есть П(л), достаточно полокить с = 1/100 и рассмотреть множество четных чисел га = О, 2, 4, б,... . D

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

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

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

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

Пример 1.7. На рис. 1.6 показаны функции времени выполнения (измеренные в секундах) для четырех программ с различной временной слокностью для одного и

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



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

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


5 10 15 20 п

Рис. 1.6. функции времени выполнения четырех программ Таблица 1.3. Эффект от 10-кратного увеличения быстродействия компьютера

Время Максимальвый размер Максимальный размер Увеличение

выполнения Tfn) задачи для 10секунд задачи для IC* секунд максимального размера

задачи

10 14 12 10

45 27 13

10.0 3.2 2.3 1.3

1.4. ВРЕМЯ ВЫПОЛНЕНИЯ ПРОГРАММ



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

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

Немного соли

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

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

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

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

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

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

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

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





0 1 2 3 4 5 [6] 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0036