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

МОДЕЛИ ВЫЧИСЛЕНИЙ

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

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

1.1. АЛГОРИТМЫ И ИХ СЛОЖНОСТИ

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

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



делить емкостную сложность и асимптотическую емкостную сложность.

Именно асимптотическая сложность алгоритма определяет в итоге размер задач, которые можно решить этим алгоритмом. Если алгоритм обрабатывает входы размера п за время сп, где с - некоторая постоянная, то говорят, что временная сложность этого алгоритма есть 0{п) (читается "порядка п*"). Точнее, говорят, что (неотрицательная) функция g(n) есть 0(f(n)), если существует такая постоянная с, что g{n)cf{n) для всех, кроме конечного (возможно, пустого) множества, неотрицательных значений п.

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

Допустим, у нас есть пять алгоритмов Ai-Л5 со следующими временными сложностями:

Алгоритм Временная сложность

Ai п

Ла nlogn*)

Л4 п»

Л, 2"

Здесь временная сложность - это число единиц времени, требуемого для обработки входа размера п. Пусть единицей времени будет одна миллисекунда. Тогда алгоритм Ai может обработать за одну секунду вход размера 1000, в то время как Л5 - вход размера не более 9. На рис. 1.1 приведены размеры задач, которые можно решить за одну секунду, одну минуту и один час каждым из этих пяти алгоритмов.

Предположим, что следующее поколение вычислительных машин будет в 10 раз быстрее нынешнего. На рис. 1.2 показано, как возрастут размеры задач, которые мы сможем решить благодаря этому увеличению скорости. Заметим, что для алгоритма Аь десятикратное увеличение скорости увеличивает размер задачи, которую можно решить, только на три, тогда как для алгоритма Л3 размер задачи более чем утраивается.

Вместо эффекта увеличения скорости рассмотрим теперь эффект применения более действенного алгоритма. Вернемся к рис. 1.1.

1) Если не оговорено противное, все логарифмы в этой книге берутся по основанию 2.



Алгоритм

Временная сложность

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

1 мин

1000

6х 10*

3,6x10»

п log п

4893

2,0x10

1897

2"

Рис. 1.1. Границы размеров задач, определяемые скоростью роста сложности.

Если в качестве основы для сравнения взять 1 мин, то, заменяя алгоритм Л4 алгоритмом As, можно решить задачу, в 6 раз большую, а заменяя Л 4 на Л г, можно решить задачу, большую в 125 раз. Эти результаты производят гораздо большее впечатление, чем двукратное улучшение, достигаемое за счет десятикратного увеличения скорости. Если в качестве основы для сравнения взять 1 ч, то различие оказывается еще значительнее. Отсюда мы заключаем, что асимптотическая сложность алгоритма служит важной мерой качественности алгоритма, причем такой мерой, которая обещает стать еще важнее при последующем увеличении скорости вычислений.

Несмотря на то что основное внимание здесь уделяется порядку роста величин, надо понимать, что большой порядок роста сложности алгоритма может иметь меньшую мультипликативную посто-

Алгоритм

Временная сложность

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

до ускорения

после ускорения

lOsi

п log п

Примерно lOsa для

больших «2

3,1 б5з

2,15s,

2"

«6

S5 + 3,3

Рис. 1.2. Эффект десятикратного ускорения.





[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 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002