Введення 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 < p> Швидке сортування 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 < p> Парадигми ООП 335
Керуючі об'єкти 335
Контролюючий об'єкт 336
ітератор 337
Дружній клас 338
Інтерфейс 340
Фасад 340
породжує об'єкт 340
Єдиний об'єкт 341
Перетворення в послідовну форму 341
Парадигма Модель/Вид/Контроллер. 344
Резюме 346
Вимоги до апаратного забезпечення 346
Виконання програм прикладів 346
[email protected]
Далі йде «текст», який будь-який поважає себе, програміст повиненпрочитати хоча б один раз. (Це наше суб'єктивна думка)
Введення
Програмування під 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
'Виконати будь-які дії.
Next K
Next J
Next I
End Sub
Sub Fast ()
Dim I As Integer
Dim J As Integer
Dim K As Integer
For I = 1 To N
For J = 1 To N
Slow 'Виклик процедури Slow.
Next J
Next I
End Sub
Sub MainProgram ()
Fast
End Sub
З іншого боку, якщо процедури, незалежно викликаються з основноїпрограми, їх обчислювальна складність підсумовується. У цьому випадку повнаскладність буде дорівнює O (N3) + O (N2) = O (N3). Таку складність, наприклад, будемати наступний фрагмент коду:
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
'Виконати будь-які дії.
Next K
Next J
Next I
End Sub
Sub Fast ()
Dim I As Integer
Dim J As Integer
For I = 1 To N
For J = 1 To N
'Виконати будь-які дії.
Next J
Next I
End Sub
Sub MainProgram ()
Slow
Fast
End Sub
============== 5
Складність рекурсивних алгоритмів
рекурсивними процедурами (recursive procedure) називаються процедури,викликають самі себе. У багатьох рекурсивних алгоритмах саме ступіньвкладеності рекурсії визначає складність алгоритму, при цьому не завждилегко оцінити порядок складності. Рекурсивна процедура може виглядатипростий, але при цьому вносити великий внесок у складність програми,багаторазово викликаючи саму себе.
Наступний фрагмент коду містить підпрограму всього з двох операторів. Тимне менше, для заданого N підпрограма виконується N раз, таким чином,обчислювальна складність фрагмента порядку O (N).
Sub CountDown (N As Integer)
If N 20 Then
ArraySize = ArraySize -10
ReDim Preserve List (1 To ArraySize)
End If
End Sub
============= 20
Для дуже великих масивів це рішення може також виявитися не самимкращим. Якщо вам потрібен список, що містить 1000 елементів, до якого зазвичайдодається по 100 елементів, то все ще надто багато часу будевитрачатися на зміну розміру масиву. Очевидною стратегією у цьому випадкубуло б збільшення збільшення розміру масиву з 10 до 100 або більше клітинок.
Тоді можна було б додавати по 100 елементів одночасно без частогозміни розміру списку.
Більш гнучким рішенням буде зміна приросту в залежності від розмірумасиву. Для невеликих списків це збільшення було б також невеликим. Хочазміни розміру масиву відбувалися б частіше, вони зажадали бвідносно небагато часу для невеликих масивів. Для великих списків,збільшення розміру буде більше, тому їх розмір буде змінюватися рідше.
Наст
