|
VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программированияVB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программированияВведение 8 Целевая аудитория 10 Глава 1. Основные понятия 15 Что такое алгоритмы? 15 Анализ скорости выполнения алгоритмов 16 Пространство — время 17 Оценка с точностью до порядка 17 Поиск сложных частей алгоритма 19 Сложность рекурсивных алгоритмов 20 Многократная рекурсия 21 Косвенная рекурсия 22 Требования рекурсивных алгоритмов к объему памяти 22 Наихудший и усредненный случай 23 Часто встречающиеся функции оценки порядка сложности 24 Логарифмы 25 Реальные условия — насколько быстро? 25 Обращение к файлу подкачки 26 Псевдоуказатели, ссылки на объекты и коллекции 27 Резюме 29 Глава 2. Списки 30 Знакомство со списками 31 Простые списки 31 Коллекции 32 Список переменного размера 33 Класс SimpleList 36 Неупорядоченные списки 37 Связные списки 41 Добавление элементов к связному списку 43 Удаление элементов из связного списка 44 Уничтожение связного списка 44 Сигнальные метки 45 Инкапсуляция связных списков 46 Доступ к ячейкам 47 Разновидности связных списков 49 Циклические связные списки 49 Проблема циклических ссылок 50 Двусвязные списки 50 Потоки 53 Другие связные структуры 56 Псевдоуказатели 56 Резюме 59 Глава 3. Стеки и очереди 60 Стеки 60 Множественные стеки 62 Очереди 63 Циклические очереди 65 Очереди на основе связных списков 69 Применение коллекций в качестве очередей 70 Приоритетные очереди 70 Многопоточные очереди 72 Резюме 74 Глава 4. Массивы 75 Треугольные массивы 75 Диагональные элементы 77 Нерегулярные массивы 78 Прямая звезда 78 Нерегулярные связные списки 79 Разреженные массивы 80 Индексирование массива 82 Очень разреженные массивы 85 Резюме 86 Глава 5. Рекурсия 86 Что такое рекурсия? 87 Рекурсивное вычисление факториалов 88 Анализ времени выполнения программы 89 Рекурсивное вычисление наибольшего общего делителя 90 Анализ времени выполнения программы 91 Рекурсивное вычисление чисел Фибоначчи 92 Анализ времени выполнения программы 93 Рекурсивное построение кривых Гильберта 94 Анализ времени выполнения программы 96 Рекурсивное построение кривых Серпинского 98 Анализ времени выполнения программы 100 Опасности рекурсии 101 Бесконечная рекурсия 101 Потери памяти 102 Необоснованное применение рекурсии 103 Когда нужно использовать рекурсию 104 Хвостовая рекурсия 105 Нерекурсивное вычисление чисел Фибоначчи 107 Устранение рекурсии в общем случае 110 Нерекурсивное построение кривых Гильберта 114 Нерекурсивное построение кривых Серпинского 117 Резюме 121 Глава 6. Деревья 121 Определения 122 Представления деревьев 123 Полные узлы 123 Списки потомков 124 Представление нумерацией связей 126 Полные деревья 129 Обход дерева 130 Упорядоченные деревья 135 Добавление элементов 135 Удаление элементов 136 Обход упорядоченных деревьев 139 Деревья со ссылками 141 Работа с деревьями со ссылками 144 Квадродеревья 145 Изменение MAX_PER_NODE 151 Использование псевдоуказателей в квадродеревьях 151 Восьмеричные деревья 152 Резюме 152 Глава 7. Сбалансированные деревья 153 Сбалансированность дерева 153 АВЛ-деревья 154 Удаление узла из АВЛ-дерева 161 Б-деревья 166 Производительность Б-деревьев 167 Вставка элементов в Б-дерево 167 Удаление элементов из Б-дерева 168 Разновидности Б-деревьев 169 Улучшение производительности Б-деревьев 171 Балансировка для устранения разбиения блоков 171 Вопросы, связанные с обращением к диску 173 База данных на основе Б+дерева 176 Резюме 179 Глава 8. Деревья решений 179 Поиск в деревьях игры 180 Минимаксный поиск 181 Улучшение поиска в дереве игры 185 Поиск в других деревьях решений 187 Метод ветвей и границ 187 Эвристики 191 Другие сложные задачи 207 Задача о выполнимости 207 Задача о разбиении 208 Задача поиска Гамильтонова пути 209 Задача коммивояжера 210 Задача о пожарных депо 211 Краткая характеристика сложных задач 212 Резюме 212 Глава 9. Сортировка 213 Общие соображения 213 Таблицы указателей 213 Объединение и сжатие ключей 215 Примеры программ 217 Сортировка выбором 219 Рандомизация 220 Сортировка вставкой 221 Вставка в связных списках 222 Пузырьковая сортировка 224 Быстрая сортировка 227 Сортировка слиянием 232 Пирамидальная сортировка 234 Пирамиды 235 Приоритетные очереди 237 Алгоритм пирамидальной сортировки 240 Сортировка подсчетом 241 Блочная сортировка 242 Блочная сортировка с применением связного списка 243 Блочная сортировка на основе массива 245 Резюме 248 Глава 10. Поиск 248 Примеры программ 249 Поиск методом полного перебора 249 Поиск в упорядоченных списках 250 Поиск в связных списках 251 Двоичный поиск 253 Интерполяционный поиск 255 Строковые данные 259 Следящий поиск 260 Интерполяционный следящий поиск 261 Резюме 262 Глава 11. Хеширование 263 Связывание 265 Преимущества и недостатки связывания 266 Блоки 268 Хранение хеш-таблиц на диске 270 Связывание блоков 274 Удаление элементов 275 Преимущества и недостатки применения блоков 277 Открытая адресация 277 Линейная проверка 278 Квадратичная проверка 284 Псевдослучайная проверка 286 Удаление элементов 289 Резюме 291 Глава 12. Сетевые алгоритмы 292 Определения 292 Представления сети 293 Оперирование узлами и связями 295 Обходы сети 296 Наименьшие остовные деревья 298 Кратчайший маршрут 302 Установка меток 304 Коррекция меток 308 Другие задачи поиска кратчайшего маршрута 311 Применения метода поиска кратчайшего маршрута 316 Максимальный поток 319 Приложения максимального потока 325 Резюме 327 Глава 13. Объектно-ориентированные методы 327 Преимущества ООП 328 Инкапсуляция 328 Полиморфизм 330 Наследование и повторное использование 333 Парадигмы ООП 335 Управляющие объекты 335 Контролирующий объект 336 Итератор 337 Дружественный класс 338 Интерфейс 340 Фасад 340 Порождающий объект 340 Единственный объект 341 Преобразование в последовательную форму 341 Парадигма Модель/Вид/Контроллер. 344 Резюме 346 Требования к аппаратному обеспечению 346 Выполнение программ примеров 346 programmer@newmail.ru Далее следует «текст», который любой уважающий себя программист должен прочесть хотя бы один раз. (Это наше субъективное мнение) Введение Программирование под Windows всегда было нелегкой задачей. Интерфейс прикладного программирования (Application Programming Interface) Windows предоставляет в распоряжение программиста набор мощных, но не всегда безопасных инструментов для разработки приложений. Можно сравнить его с бульдозером, при помощи которого удается добиться поразительных результатов, но без соответствующих навыков и осторожности, скорее всего, дело закончится только разрушениями и убытками. Эта картина изменилась с появлением Visual Basic. Используя визуальный интерфейс, Visual Basic позволяет быстро и легко разрабатывать законченные приложения. При помощи Visual Basic можно разрабатывать и тестировать сложные приложения без прямого использования функций API. Избавляя программиста от проблем с API, Visual Basic позволяет сконцентрироваться на деталях приложения. Хотя Visual Basic и облегчает разработку пользовательского интерфейса, задача написания кода для реакции на входные воздействия, обработки их, и представления результатов ложится на плечи программиста. Здесь начинается применение алгоритмов. Алгоритмы представляют собой формальные инструкции для выполнения сложных задач на компьютере. Например, алгоритм сортировки может определять, как найти конкретную запись в базе из 10 миллионов записей. В зависимости от класса используемых алгоритмов искомые данные могут быть найдены за секунды, часы или вообще не найдены. В этом материале обсуждаются алгоритмы на Visual Basic и содержится большое число мощных алгоритмов, полностью написанных на этом языке. В ней также анализируются методы обращения со структурами данных, такими, как списки, стеки, очереди и деревья, и алгоритмы для выполнения типичных задач, таких как сортировка, поиск и хэширование. Для того чтобы успешно применять эти алгоритмы, недостаточно их просто скопировать в свою программу. Необходимо кроме этого понимать, как различные алгоритмы ведут себя в разных ситуациях, что в конечном итоге и будет определять выбор наиболее подходящего алгоритма. В этом материале поведение алгоритмов в типичном и наихудшем случаях описано доступным языком. Это позволит понять, чего вы вправе ожидать от того или иного алгоритма и распознать, в каких условиях встречается наихудший случай, и в соответствии с этим переписать или поменять алгоритм. Даже самый лучший алгоритм не поможет в решении задачи, если применять его неправильно. =============xi Все алгоритмы также представлены в виде исходных текстов на Visual Basic, которые вы можете использовать в своих программах без каких-либо изменений. Они демонстрируют использование алгоритмов в программах, а также важные характерные особенности работы самих алгоритмов. Что дают вам эти знания После ознакомления с данным материалом и примерами вы получите: 1. Понятие об алгоритмах. После прочтения данного материала и выполнения примеров программ, вы сможете применять сложные алгоритмы в своих проектах на Visual Basic и критически оценивать другие алгоритмы, написанные вами или кем-либо еще. 2. Большую подборку исходных текстов, которые вы сможете легко добавить к вашим программам. Используя код, содержащийся в примерах, вы сможете легко добавлять мощные алгоритмы к вашим приложениям. 3. Готовые примеры программ дадут вам возможность протестировать алгоритмы. Вы можете использовать эти примеры и модифицировать их для углубленного изучения алгоритмов и понимания их работы, или использовать их как основу для разработки собственных приложений. Целевая аудитория В этом материале обсуждаются углубленные вопросы программирования на Visual Basic. Они не предназначена для обучения программированию на этом языке. Если вы хорошо разбираетесь в основах программирования на Visual Basic, вы сможете сконцентрировать внимание на алгоритмах вместо того, чтобы застревать на деталях языка. В этом материале изложены важные концепции программирования, которые могут быть с успехом применены для решения новых задач. Приведенные алгоритмы используют мощные программные методы, такие как рекурсия, разбиение на части, динамическое распределение памяти и сетевые структуры данных, которые вы можете применять для решения своих конкретных задач. Даже если вы еще не овладели в полной мере программированием на Visual Basic, вы сможете скомпилировать примеры программ и сравнить производительность различных алгоритмов. Более того, вы сможете выбрать удовлетворяющие вашим требованиям алгоритмы и добавить их к вашим проектам на Visual Basic. Совместимость с разными версиями Visual Basic Выбор наилучшего алгоритма определяется не особенностями версии языка программирования, а фундаментальными принципами программирования. =================xii Некоторые новые понятия, такие как ссылки на объекты, классы и коллекции, которые были впервые введены в 4-й версии Visual Basic, облегчают понимание, разработку и отладку некоторых алгоритмов. Классы могут заключать некоторые алгоритмы в хорошо продуманных модулях, которые легко вставить в программу. Хотя для того, чтобы применять эти алгоритмы, необязательно разбираться в новых понятиях языка, эти новые возможности предоставляют слишком большие преимущества, чтобы ими можно было пренебречь. Поэтому примеры алгоритмов в этом материале написаны для использования в 4- й и 5-й версиях Visual. Если вы откроете их в 5-й версии Visual Basic, среда разработки предложит вам сохранить их в формате 5-й версии, но никаких изменений в код вносить не придется. Все алгоритмы были протестированы в обеих версиях. Эти программы демонстрируют использование алгоритмов без применения объектно-ориентированного подхода. Ссылки и коллекции облегчают программирование, но их применение может приводить к некоторому замедлению работы программ по сравнению со старыми версиями. Тем не менее, игнорирование классов, объектов и коллекций привело бы к упущению многих действительно мощных свойств. Их использование позволяет достичь нового уровня модульности, разработки и повторного использования кода. Их, безусловно, необходимо иметь в виду, по крайней мере, на начальных этапах разработки. В дальнейшем, если возникнут проблемы с производительностью, вы сможете модифицировать код, используя более быстрые низкоуровневые методы. Языки программирования зачастую развиваются в сторону усложнения, но редко в противоположном направлении. Замечательным примером этого является наличие оператора goto в языке C. Это неудобный оператор, потенциальный источник ошибок, который почти не используется большинством программистов на C, но он по-прежнему остается в синтаксисе языка с 1970 года. Он даже был включен в C++ и позднее в Java, хотя создание нового языка было хорошим предлогом избавиться от него. Так и новые версии Visual Basic будут продолжать вводить новые свойства в язык, но маловероятно, что из них будут исключены строительные блоки, использованные при применении алгоритмов, описанных в данном материале. Независимо от того, что будет добавлено в 6-й, 7-й или 8-й версии Visual Basic, классы, массивы и определяемые пользователем типы данных останутся в языке. Большая часть, а может и все алгоритмы из приведенных ниже, будут выполняться без изменений в течение еще многих лет. Обзор глав В 1 главе рассматриваются понятия, которые вы должны понимать до того, как приступить к анализу сложных алгоритмов. В ней изложены методы, которые потребуются для теоретического анализа вычислительной сложности алгоритмов. Некоторые алгоритмы с высокой теоретической производительностью на практике дают не очень хорошие результаты, поэтому в этой главе также затрагиваются практические соображения, например обращение к файлу подкачки и сравнивается использование коллекций и массивов. Во 2 главе показано, как образуются различные виды списков с использованием массивов, объектов, и псевдоуказателей. Эти структуры данных можно с успехом применять во многих программах, и они используются в следующих главах В 3 главе описаны два особых типа списков: стеки и очереди. Эти структуры данных используются во многих алгоритмах, включая некоторые алгоритмы, описанные в последующих главах. В конце главы приведена модель очереди на регистрацию в аэропорту. В 5 главе обсуждается мощный инструмент — рекурсия. Рекурсия может быть также запутанной и приводить к проблемам. В 5 главе объясняется, в каких случаях следует применять рекурсию и показывает, как можно от нее избавиться, если это необходимо. В 6 главе используются многие из ранее описанных приемов, такие как рекурсия и связные списки, для изучения более сложной темы — деревьев. Эта глава также охватывает различные представления деревьев, такие как деревья с полными узлами (fat node) и представление в виде нумерацией связей (forward star). В ней также описаны некоторые важные алгоритмы работы с деревьями, таки как обход вершин дерева. В 7 главе затронута более сложная тема. Сбалансированные деревья обладают особыми свойствами, которые позволяют им оставаться уравновешенными и эффективными. Алгоритмы сбалансированных деревьев удивительно просто описываются, но их достаточно трудно реализовать программно. В этой главе используется одна из наиболее мощных структур подобного типа — Б+дерево (B+Tree) для создания сложной базы данных. В 8 главе обсуждаются задачи, которые можно описать как поиск ответов в дереве решений. Даже для небольших задач, эти деревья могут быть гигантскими, поэтому необходимо осуществлять поиск в них максимально эффективно. В этой главе сравниваются некоторые различные методы, которые позволяют выполнить такой поиск. Глава 9 посвящена, пожалуй, наиболее изучаемой области теории алгоритмов — сортировке. Алгоритмы сортировки интересны по нескольким причинам. Во-первых, сортировка — часто встречающаяся задача. Во-вторых, различные алгоритмы сортировок обладают своими сильными и слабыми сторонами, поэтому не существует одного алгоритма, который показывал бы наилучшие результаты в любых ситуациях. И, наконец, алгоритмы сортировки демонстрируют широкий спектр важных алгоритмических методов, таких как рекурсия, пирамиды, а также использование генератора случайных чисел для уменьшения вероятности выпадения наихудшего случая. В главе 10 рассматривается близкая к сортировке тема. После выполнения сортировки списка, программе может понадобиться найти элементы в нем. В этой главе сравнивается несколько наиболее эффективных методов поиска элементов в сортированных списках. =========xiv В главе 11 обсуждаются методы сохранения и поиска элементов, работающие даже быстрее, чем это возможно при использовании деревьев, сортировки или поиска. В этой главе также описаны некоторые методы хэширования, включая использование блоков и связных списков, и несколько вариантов открытой адресации. В главе 12 описана другая категория алгоритмов — сетевые алгоритмы. Некоторые из этих алгоритмов, такие как вычисление кратчайшего пути, непосредственно применимы к физическим сетям. Эти алгоритмы также могут косвенно применяться для решения других задач, которые на первый взгляд не кажутся связанными с сетями. Например, алгоритмы поиска кратчайшего расстояния могут разбивать сеть на районы или определять критичные задачи в расписании проекта. В главе 13 объясняются методы, применение которых стало возможным благодаря введению классов в 4-й версии Visual Basic. Эти методы используют объектно- ориентированный подход для реализации нетипичного для традиционных алгоритмов поведения. ===================xv Аппаратные требования Для работы с примерами вам потребуется компьютер, конфигурация которого удовлетворяет требованиям для работы программной среды Visual Basic. Эти требования выполняются почти для всех компьютеров, на которых может работать операционная система Windows. На компьютерах разной конфигурации алгоритмы выполняются с различной скоростью. Компьютер с процессором Pentium Pro с тактовой частотой 2000 МГц и 64 Мбайт оперативной памяти будет работать намного быстрее, чем машина с 386 процессором и всего 4 Мбайт памяти. Вы быстро узнаете, на что способно ваше аппаратное обеспечение. Изменения во втором издании Самое большое изменение в новой версии Visual Basic — это появление классов. Классы позволяют рассмотреть некоторые задачи с другой стороны, позволяя использовать более простой и естественный подход к пониманию и применению многих алгоритмов. Изменения в коде программ в этом изложении используют преимущества, предоставляемые классами. Их можно разбить на три категории: 1. Замена псевдоуказателей классами. Хотя все алгоритмы, которые были написаны для старых версий VB, все еще работают, многие из тех, что были написаны с применением псевдоуказателей (описанных во 2 главе), гораздо проще понять, используя классы. 2. Инкапсуляция. Классы позволяют заключить алгоритм в компактный модуль, который легко использовать в программе. Например, при помощи классов можно создать несколько связных списков и не писать при этом дополнительный код для управления каждым списком по отдельности. 3. Объектно-ориентированные технологии. Использование классов также позволяет легче понять некоторые объектно-ориентированные алгоритмы. В главе 13 описываются методы, которые сложно реализовать без использования классов. Как пользоваться этим материалом В главе 1 даются общие понятия, которые используются на протяжении всего изложения, поэтому вам следует начать чтение с этой главы. Вам стоит ознакомиться с этой тематикой, даже если вы не хотите сразу же достичь глубокого понимания алгоритмов. В 6 главе обсуждаются понятия, которые используются в 7, 8 и 12 главах, поэтому вам следует прочитать 6 главу до того, как браться за них. Остальные главы можно читать в любом порядке. =============xvi В табл. 1 показаны три возможных учебных плана, которыми вы можете руководствоваться при изучении материала в зависимости от того, насколько широко вы хотите ознакомиться с алгоритмами. Первый план включает в себя освоение основных методов и структур данных, которые могут быть полезны при разработке вами собственных программ. Второй кроме этого описывает также основные алгоритмы, такие как алгоритмы сортировки и поиска, которые могут понадобиться при написании более сложных программ. Последний план дает порядок для изучения всего материала целиком. Хотя 7 и 8 главы логически вытекают из 6 главы, они сложнее для изучения, чем следующие главы, поэтому они изучаются несколько позже. Почему именно Visual Basic? Наиболее часто встречаются жалобы на медленное выполнение программ, написанных на Visual Basic. Многие другие компиляторы, такие как Delphi, Visual C++ дают более быстрый и гибкий код, и предоставляют программисту более мощные средства, чем Visual Basic. Поэтому логично задать вопрос — «Почему я должен использовать именно Visual Basic для написания сложных алгоритмов? Не лучше было бы использовать Delphi или C++ или, по крайней мере, написать алгоритмы на одном из этих языков и подключать их к программам на Visual Basic при помощи библиотек?» Написание алгоритмов на Visual Basic имеет смысл по нескольким причинам. Во-первых, разработка приложения на Visual C++ гораздо сложнее и проблематичнее, чем на Visual Basic. Некорректная реализация в программе всех деталей программирования под Windows может привести к сбоям в вашем приложении, среде разработки, или в самой операционной системе Windows. Во-вторых, разработка библиотеки на языке C++ для использования в программах на Visual Basic включает в себя много потенциальных опасностей, характерных и для приложений Windows, написанных на C++. Если библиотека будет неправильно взаимодействовать с программой на Visual Basic, она также приведет к сбоям в программе, а возможно и в среде разработки и системе. В-третьих, многие алгоритмы достаточно эффективны и показывают неплохую производительность даже при применении не очень быстрых компиляторов, таких, как Visual Basic. Например, алгоритм сортировки подсчетом, @Таблица 1. Планы занятий ===============xvii описываемый в 9 главе, сортирует миллион целых чисел менее чем за 2 секунды на компьютере с процессором Pentium с тактовой частотой 233 МГц. Используя библиотеку C++, можно было бы сделать алгоритм немного быстрее, но скорости версии на Visual Basic и так хватает для большинства приложений. Скомпилированные при помощи 5-й версией Visual Basic исполняемые файлы сводят отставание по скорости к минимуму. В конечном счете, разработка алгоритмов на любом языке программирования позволяет больше узнать об алгоритмах вообще. По мере изучения алгоритмов, вы освоите методы, которые сможете применять в других частях своих программ. После того, как вы овладеете в совершенстве алгоритмами на Visual Basic, вам будет гораздо легче реализовать их на Delphi или C++, если это будет необходимо. =============xviii Глава 1. Основные понятия В этой главе содержатся общие понятия, которые нужно усвоить перед началом серьезного изучения алгоритмов. Начинается она с вопроса «Что такое алгоритмы?». Прежде чем углубиться в детали программирования алгоритмов, стоит потратить немного времени, чтобы разобраться в том, что это такое. Затем в этой главе дается введение в формальную теорию сложности алгоритмов (complexity theory). При помощи этой теории можно оценить теоретическую вычислительную сложность алгоритмов. Этот подход позволяет сравнивать различные алгоритмы и предсказывать их производительность в разных условиях. В главе приводится несколько примеров применения теории сложности к небольшим задачам. Некоторые алгоритмы с высокой теоретической производительностью не слишком хорошо работают на практике, поэтому в данной главе также обсуждаются некоторые реальные предпосылки для создания программ. Слишком частое обращение к файлу подкачки или плохое использование ссылок на объекты и коллекции может значительно снизить производительность прекрасного в остальных отношениях приложения. После знакомства с основными понятиями, вы сможете применять их к алгоритмам, изложенным в последующих главах, а также для анализа собственных программ для оценки их производительности и сможете предугадывать возможные проблемы до того, как они обернутся катастрофой. Что такое алгоритмы? Алгоритм – это последовательность инструкций для выполнения какого-либо задания. Когда вы даете кому-то инструкции о том, как отремонтировать газонокосилку, испечь торт, вы тем самым задаете алгоритм действий. Конечно, подобные бытовые алгоритмы описываются неформально, например, так: Проверьте, находится ли машина на стоянке. Убедитесь, что машина поставлена на ручной тормоз. Поверните ключ. И т.д. ==========1 При этом по умолчанию предполагается, что человек, который будет следовать этим инструкциям, сможет самостоятельно выполнить множество мелких операций, например, отпереть и открыть дверь, сесть за руль, пристегнуть ремень, найти ручной тормоз и так далее. Если же составляется алгоритм для исполнения компьютером, вы не можете полагаться на то, что компьютер поймет что-либо, если это не описано заранее. Словарь компьютера (язык программирования) очень ограничен и все инструкции для компьютера должны быть сформулированы на этом языке. Поэтому для написания компьютерных алгоритмов используется формализованный стиль. Интересно попробовать написать формализованный алгоритм для обычных ежедневных задач. Например, алгоритм вождения машины мог бы выглядеть примерно так: Если дверь закрыта: Вставить ключ в замок Повернуть ключ Если дверь остается закрытой, то: Повернуть ключ в другую сторону Повернуть ручку двери И т.д. Этот фрагмент «кода» отвечает только за открывание двери; при этом даже не проверяется, какая дверь открывается. Если дверь заело или в машине установлена противоугонная система, то алгоритм открывания двери может быть достаточно сложным. Формализацией алгоритмов занимаются уже тысячи лет. За 300 лет до н.э. Евклид написал алгоритмы деления углов пополам, проверки равенства треугольников и решения других геометрических задач. Он начал с небольшого словаря аксиом, таких как «параллельные линии не пересекаются» и построил на их основе алгоритмы для решения сложных задач. Формализованные алгоритмы такого типа хорошо подходят для задач математики, где должна быть доказана истинность какого-либо положения или возможность выполнения каких-то действий, скорость же исполнения алгоритма не важна. Для выполнения реальных задач, связанных с выполнением инструкций, например задачи сортировки на компьютере записей о миллионе покупателей, эффективность выполнения становится важной частью постановки задачи. Анализ скорости выполнения алгоритмов Есть несколько способов оценки сложности алгоритмов. Программисты обычно сосредотачивают внимание на скорости алгоритма, но важны и другие требования, например, к размеру памяти, свободному месту на диске или другим ресурсам. От быстрого алгоритма может быть мало толку, если под него требуется больше памяти, чем установлено на компьютере. Пространство — время Многие алгоритмы предоставляют выбор между скоростью выполнения и используемыми программой ресурсами. Задача может выполняться быстрее, используя больше памяти, или наоборот, медленнее, заняв меньший объем памяти. ===========2 Хорошим примером в данном случае может служить алгоритм нахождения кратчайшего пути. Задав карту улиц города в виде сети, можно написать алгоритм, вычисляющий кратчайшее расстояние между любыми двумя точками в этой сети. Вместо того чтобы каждый раз заново пересчитывать кратчайшее расстояние между двумя заданными точками, можно заранее просчитать его для всех пар точек и сохранить результаты в таблице. Тогда, чтобы найти кратчайшее расстояние для двух заданных точек, достаточно будет просто взять готовое значение из таблицы. При этом мы получим результат практически мгновенно, но это потребует большого объема памяти. Карта улиц для большого города, такого как Бостон или Денвер, может содержать сотни тысяч точек. Для такой сети таблица кратчайших расстояний содержала бы более 10 миллиардов записей. В этом случае выбор между временем исполнения и объемом требуемой памяти очевиден: поставив дополнительные 10 гигабайт оперативной памяти, можно заставить программу выполняться гораздо быстрее. Из этой связи вытекает идея пространственно-временной сложности алгоритмов. При этом подходе сложность алгоритма оценивается в терминах времени и пространства, и находится компромисс между ними. В этом материале основное внимание уделяется временной сложности, но мы также постарались обратить внимание и на особые требования к объему памяти для некоторых алгоритмов. Например, сортировка слиянием (mergesort), обсуждаемая в 9 главе, требует больше временной памяти. Другие алгоритмы, например пирамидальная сортировка (heapsort), которая также обсуждается в 9 главе, требует обычного объема памяти. Оценка с точностью до порядка При сравнении различных алгоритмов важно понимать, как сложность алгоритма соотносится со сложностью решаемой задачи. При расчетах по одному алгоритму сортировка тысячи чисел может занять 1 секунду, а сортировка миллиона — 10 секунд, в то время как расчеты по другому алгоритму могут потребовать 2 и 5 секунд соответственно. В этом случае нельзя однозначно сказать, какая из двух программ лучше — это будет зависеть от исходных данных. Различие производительности алгоритмов на задачах разной вычислительной сложности часто более важно, чем просто скорость алгоритма. В вышеприведенном случае, первый алгоритм быстрее сортирует короткие списки, а второй — длинные. Производительность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность порядка O(f(N)) (произносится «О большое от F от N»), если время выполнения алгоритма растет пропорционально функции f(N) с увеличением размерности исходных данных N. Например, рассмотрим фрагмент кода, сортирующий положительные числа: For I = 1 To N 'Поиск наибольшего элемента в списке. MaxValue = 0 For J = 1 to N If Value(J) > MaxValue Then MaxValue = Value(J) MaxJ = J End If Next J 'Вывод наибольшего элемента на печать. Print Format$(MaxJ) & ":" & Str$(MaxValue) 'Обнуление элемента для исключения его из дальнейшего поиска. Value(MaxJ) = 0 Next I ===============3 В этом алгоритме переменная цикла I последовательно принимает значения от 1 до N. Для каждого приращения I переменная J в свою очередь также принимает значения от 1 до N. Таким образом, в каждом внешнем цикле выполняется еще N внутренних циклов. В итоге внутренний цикл выполняется N*N или N2 раз и, следовательно, сложность алгоритма порядка O(N2). При оценке порядка сложности алгоритмов используется только наиболее быстро растущая часть уравнения алгоритма. Допустим, время выполнения алгоритма пропорционально N3+N. Тогда сложность алгоритма будет равна O(N3). Отбрасывание медленно растущих частей уравнения позволяет оценить поведение алгоритма при увеличении размерности данных задачи N. При больших N вклад второй части в уравнение N3+N становится все менее заметным. При N=100, разность N3+N=1.000.100 и N3 равна всего 100, или менее чем 0,01 процента. Но это верно только для больших N. При N=2, разность между N3+N =10 и N3=8 равна 2, а это уже 20 процентов. Постоянные множители в соотношении также игнорируются. Это позволяет легко оценить изменения в вычислительной сложности задачи. Алгоритм, время выполнения которого пропорционально 3*N2, будет иметь порядок O(N2). Если увеличить N в 2 раза, то время выполнения задачи возрастет примерно в 22, то есть в 4 раза. Игнорирование постоянных множителей позволяет также упростить подсчет числа шагов алгоритма. В предыдущем примере внутренний цикл выполняется N2 раз, при этом внутри цикла выполняется несколько инструкций. Можно просто подсчитать число инструкций If, можно подсчитать также инструкции, выполняемые внутри цикла или, кроме того, еще и инструкции во внешнем цикле, например операторы Print. Вычислительная сложность алгоритма при этом будет пропорциональна N2, 3*N2 или 3*N2+N. Оценка сложности алгоритма по порядку величины даст одно и то же значение O(N3) и отпадет необходимость в точном подсчете количества операторов. Поиск сложных частей алгоритма Обычно наиболее сложным является выполнение циклов и вызовов процедур. В предыдущем примере, весь алгоритм заключен в двух циклах. ============4 Если процедура вызывает другую процедуру, необходимо учитывать сложность вызываемой процедуры. Если в ней выполняется фиксированное число инструкций, например, осуществляется вывод на печать, то при оценке порядка сложности ее можно не учитывать. С другой стороны, если в вызываемой процедуре выполняется O(N) шагов, она может вносить значительный вклад в сложность алгоритма. Если вызов процедуры осуществляется внутри цикла, этот вклад может быть еще больше. Приведем в качестве примера программу, содержащую медленную процедуру Slow со сложностью порядка O(N3) и быструю процедуру Fast со сложностью порядка O(N2). Сложность всей программы будет зависеть от соотношения между этими двумя процедурами. Если процедура Slow вызывается в каждом цикле процедуры Fast, порядки сложности процедур перемножаются. В этом случае сложность алгоритма равна произведению O(N2) и O(N3) или O(N3*N2)=O(N5). Приведем иллюстрирующий этот случай фрагмент кода: Sub Slow() Dim I As Integer Dim J As Integer Dim K As Integer For I = 1 To N For J = 1 To N For K = 1 To N ' Выполнить какие-либо действия. |
|
