Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

Надалі в оцінках ефективності роботи алгоритмів будемо використовувати логарифмічну функцію за основою 2 і позна-чатимемо ЇЇ log₂x.

Таким чином, ми визначили, якою повинна бути оцінка оптимальності алгоритму упорядкування будь-якої послідов-ності з Л^ елементів. Тепер знаємо, що будь-який алгоритм сортування, який дає правильний результат за N • log.^N опера­щи, є найкращим і його можна вважати оптимальним. Алго-ритми, які визначають результат задачі за меншу кількість операцій, необхідно детально дослідити. Можливо, за основу такого алгоритму було взято щось інше, ніж порівняння на кожному кроці двох елементів, як у нашому випадку.

Як записується оцінка ефективності алгоритму, дізнаємося далі. Поки що зробимо висновок: для сформульованої задачі будувати дерево розв'язків щодо кожного можливого задания вхідної інформації нереально. Треба намагатися визначати оцінку оптимального розв'язку аналітично.

Узагальнення та аналіз екстремальних ситуацій

У попередніх пояснениях використовувалося поняття «опе-рація». Зупинимося детальніше на тому, які дії алгоритму вважати операціями і які треба враховувати при обчисленні оцінки нашого алгоритму.

Традиційно вважається, що значущими є операції двох ти-пів: порівняння та арифметичні операції.

Усі операції порівняння вважаються еквівалентними за ча­сом виконання. Найчастіше ці операції використовуються в операторах умовного переходу та повторенні.

Арифметичні операції, у свою чергу, діляться на дві групи:

• додавання, віднімання, збільшення та зменшення лічиль-ника;

• множення, ділення, отримання залишку по модулю.

10

Такий поділ пов'язаний з тим, що множення виконується довше, ніж додавання. Висновок: перевагу мають ті алгоритми, в яких мінімально використовуються операції другої арифмс-тичної групи.

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

Але оскільки ми вже торкнулися питания вхідних даних, то поговоримо про найкращий, найгірший та середній випадки щодо розташування в них елементів.

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

Найгіршим випадком для наведених прикладів є пошук еле­мента, який розміщений у заданій послідовності на останньому місці або його зовсім там немає, та упорядкування за зростан-ням вхідної послідовності, яка упорядкована за спаданиям. Аналіз найгіршого випадку дає верхні оцінки для часу роботи досліджуваного алгоритму. Для задачі пошуку заданого еле­мента в послідовності треба буде зробити N порівнянь, а для за­дач! упорядкування — N².

Визначення середнього випадку є найскладнішим. В основі аналізу середнього випадку лежить поділ на групи різних вхід-них даних. У кожній із таких груп містяться однотипні варіан-ти вхідних даних, тобто такі, які дають результат за однакову кількість операцій.

Розглянемо приклад задачі пошуку заданого елемента у вхідній послідовності, що складається з N елементів. Які мо-жуть бути варіанти вхідних даних, тобто послідовностей, і за яку кількість операцій вони дадуть правильну відповідь? Якщо шуканий елемент стоїть на першому місці, то за одну операцію; якщо на другому, то за дві; якщо на третьему, то за три і т. д. Якщо на останньому, то відповідь отримаємо за N операцій. Зрозуміло, що всі ці варіанти вхідних даних неможливо роз-містити в одній групі. Усі вони різні, і груп буде стільки, скіль-ки варіантів вхідних даних, тобто N.

11

На другому кроці аналізу середнього випадку нам треба ви-значити ймовірність належності кожного варіанта вхідних да-них визначеній групі. Найчастіше така ймовірність однакова

1

для всіх варіантів вхідних даних і вважається рівною —, де

М М — кількість груп. У напіій задачі ймовірність потрапляння

1 кожного варіанта у свою групу дорівнює —.

N У загальному випадку вхідні дані однієї групи мають однако-

вий час виконання t_t, оскільки саме за цією умовою ми поділили їх на групи, тому середній час роботи обчислюється за формулою:

1 ^м

Мы Шдставимо в наведену формулу дані нашої задачі. Умовно вважатимемо, що час виконання кожного варіанта вхідних да­них дорівнює кількості виконуваних операцій: для першого випадку - 1 операція, для другого - 2 і т. д. Тому сума кількос-ті операцій, виконуваних для кожного варіанта вхідних даних, виглядае як 1 + 2 + 3 + ... + (N - 1) + N. Загальна формула для визначення кількості виконуваних операцій для середнього ви­падку нашої задачі виглядае так:

N

Значения арифметичного виразу 2*' = 1+2 + 3 + ... +

+ (N - 1) + N можна замінити компактною формулою. Для цього розв'яжемо таку задачу.

Нехай треба знайти х, де х = 1 + 2 + 3 + ... + (N - 1) + N. До-дамо до даного виразу ще такий самий, але доданки розмістимо у зворотному порядку. Відповідно шукана сума збільшиться вдвічі: 2x-[l + 2 + 3 + ... + (N-l) + N\ + [N + (N-l) + ... + 3 + + 2 + 1]. Згрупуємо доданки у двох квадратних дужках: до пер­шого доданка першої дужки додамо перший доданок другої і т. д. Отримаємо: 2х - [1 + N] + [2 + {N - 1)] + ... + [N + 1] = - N(N + 1). Тепер уже нескладно знайти невідоме:

N(N + 1)

Отже, можемо визначити середній час роботи алгоритму:

1 N(N + 1) N + 1 N _пс N

5 '- = = — + 0,5 = —.

N 2 2 2 2

Часом виконання пошуку заданого елемента в будь-якій вхід-

•* N

нш послідовності в середньому випадку можна вважати —,

2

оскільки для великих значень N числом 0,5 можна знехтувати.

12

Для деяких задач обчислити середній час роботи досить складно. Найчастіше в таких ситуаціях визначають час для найгіршого випадку і орієнтуються саме на нього. До таких задач належить і задача упорядкування вхідних даних. Як ви-значити час виконання цієї задачі, дізнаємося далі.

Оцінка та аналіз ефективності алгоритму

Давайте спочатку домовимося, які саме алгоритми будемо порівнювати і як це робитимемо.

Порівнювати можна лише алгоритми, призначені для роз-в'язування однієї і тієї самої задачі. Абсолютно недоречно порівнювати алгоритм пошуку заданої величини у відомій послідовності елементів з алгоритмом її упорядкування. А от порівнювати між собою різні алгоритми сортування послідов-ностей - зовсім інша справа. Це вже логічно.

Тепер треба визначитися з питаниям: що вважати критеріями ефективності виконання алгоритму? На думку приходить досить природна відповідь: час виконання алгоритму. Але насправді це досить суб'єктивна оцінка, оскільки вона пропорційна тех-нічним характеристикам комп'ютера, на якому виконусться алгоритм, а саме тактовій частоті процесора. Ще одним факто­ром, який впливає на час виконання алгоритму, є якість ком-пілятора, що оптимізує виконуваний код алгоритму. У разі перенесения одного і того самого алгоритму з «повільного» комп'ютера на більш «швидкий» мало що зміниться в самому алгоритмі: від цього він не стане ані кращим, ані гіршим.

Що ж тоді є визначальним у ефективності виконання алго­ритму? Це не реальна кількість секунд або інших інтервалів часу, а приблизна кількість операцій, що виконусться даним алгоритмом. Саме цей фактор будемо вважати «часом», який визначає ефективність алгоритму, що, відповідно, породжу-ється його складністю.

Не останнім фактором, який впливає на швидкість виконан­ня алгоритму, є використання додаткової пам'яті. А її інколи не вистачає. Тому, аналізуючи ефективність алгоритму, будемо дивитися на необхідність використання додаткової пам'яті, як на його недолік. Надалі будемо надавати перевагу не тільки тим алгоритмам, які використовують меншу кількість порівнянь, обмінів значениями між двома змінними, а й додаткових змін-них. Звичайно, що під час аналізу ефективності виконання алгоритмів нас у першу чергу цікавитиме питания часу. Однак у тих випадках, коли пам'ять відіграє суттєву роль, значно зву-жуючи область застосування алгоритму, будемо обговорювати і ЇЇ.

Перейдемо до детального обговорення питания щодо визна-чення ефективності виконання алгоритму.

13

Оскільки основним призначенням алгоритмів є обробка вхідної інформації, то для кожного з них оцінюватимемо, на-скільки швидко розв'язується задача на масиві вхідних даних довжиною в N елементів. Наприклад, можна оцінити, скільки порівнянь вимагатиме алгоритм сортування за зростанням послідовності з N елементів, або підрахувати, скільки арифме-тичних операцій треба виконати для визначення поелементної суми двох послідовностей no N елементів кожна.

Для невеликих N, наприклад N ■ 10, кількість таких опера-цій можна порахувати точно. Але чи є в цьому потреба? Відмін-ність між алгоритмом, який виконує N + 5 операцій, і тим, що виконує N + 250 операцііі для великих N, наприклад N = 100 000, стає непомітною! Тому можна зробити висновок: якщо формула N + С для обчислення кількості виконуваних операцій алго­ритму містить константу С, нею можна знехтувати.

Постає запитання: чи варто обчислювати фактичну кількість операцій алгоритму на конкретних вхідних даних? Насправді це невдячна робота. Натомість нас цікавитиме залежність кількості операцій конкретного алгоритму від кількості вхід-них даних, а саме, як збільшується кількість операцій при збільшенні кількості вхідних даних.

Наприклад, нехай два алгоритми А та В розв'язують одну й ту саму задачу та дають можливість отримати очікуваний результат. Причому алгоритм А - за N переглядів масиву з N елементів, а алгоритм В - за N² переглядів тих саме N еле-ментів. Нехай відомо, що алгоритм А вимагає значно більшої кількості операцій, ніж алгоритм В (умовно А » В). Для прикладу вважатимемо, що алгоритм А виконує задачу за 100 операцій, а алгоритм В - за 10. Надалі порівнюватимемо їх щодо швидкості росту загальної кількості операцій.

При невеликих значениях N, наприклад N = 5, алгоритм В може бути ефективнішим за алгоритм А: для отримання ре­зультату алгоритмуА необхідно виконати 500 операцій, а алго­ритму В - 250. Якщо збільшувати N, то рано чи пізно алгоритм А програє алгоритмові В за часом роботи. Якщо взяти N = 100, то алгоритм А вимагатиме виконання 10 000 операцій, а алго­ритм В -N²" 100 000.

Отже, можна зробити висновок: саме швидкість росту відіграє ключову роль, оскільки при зростанні обсягу вхідних даних ситуація щодо кількості виконуваних операцій алго­ритмом порівняно з невеликим їх обсягом може значно зрости. Така характеристика називається швидкістю росту часу роботи алгоритму, або порядком росту часу роботи алго­ритму.

Як визначати порядок росту часу роботи алгоритму і як його позначати? Для цього найкраще розглянути конкретний

14

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

Пояснимо, як визначити кількість повторювань на кожному кроці алгоритму.

Призначенням кроку 1 є організація циклу, що виконується (N - 1) разів. Але оскільки виконання оператора повторения передбачає і перевірку завершения роботи циклу, то кількість таких дій збільшується на 1. Тобто загальна кількість повто­рень кроку 1 складає N.

Кроки 2, 3 та 6 виконуються у циклі, визначеному кроком 1, (N -1) разів.

На окрему увагу заслуговують кроки 4 і 5. У найгіршому ви-падку, коли всі елементи вхідного масиву повинні бути пере­ставлен! на перше місце, тобто буде виконана максимальна кількість переміщень для кожного елемента масиву. Перегляд елементів масиву починається з другого елемента, і цикл кроку 4 виглядатиме так: forj := 1 to 1. Це означає, що даний крок ви-конається двічі: один раз сам цикл, другий - перевірка на його завершения. Для другого елемента масиву буде виконуватися цикл forj := 1 to 2, і кількість виконуваних ним дій складатиме 3. Для останнього iV-ro елемента цикл for j := 1 to N - 1 вимагати-ме N звернень до кроку 4. Таким чином, загальна кількість ви­конання кроку 4 складатиме 2 + 3 + ... + N. Ми вже раніше виводили формулу для обчислення суми 1 + 2 + 3 + ... + N=

(1 + N)N z • Скориставшись тим самим алгоритмом для нашого

(2 + iV)(iV-l) випадку, отримаемо .

15

Використовуючи попередні міркування, можна стверджува-

ти, що крок 5 у найгіршому випадку виконається за 1 + 2 + 3 +

+ ... + (N - 1) разів. Обчислити загальну кількість виконан-

N(N-1) ня кроку 5 можна за формулою .

В

Таким чином, загальний час виконання нашого алгоритму складає:

T(N) = c_lN + c₂(N-l) + c_s(N-l) + c^^{2 + N}'^^N~¹' +

N(N-l)

Яким чином визначити порядок росту часу роботи цього ал­горитму? Розглянемо його виконання у таких трьох випадках:

• найкращому: елементи вхідного масиву утворюють упо-рядковану за зростанням послідовність;

• найгіршому: елементи вхідного масиву утворюють упо-рядковану за спаданиям послідовність;

• середньому: елементи вхідного масиву утворюють послі-довність, згенеровану випадковим чином.

У першому випадку треба буде лише переглянути всі еле­менти масиву і залишити їх на своїх місцях, тобто кроки 4—5 не виконаються жодного разу. Загальний час виконання алго­ритму в такому випадку становитиме:

T(N) = c_tN + c₂{N - 1) + c₃{N - 1) + c_e(N - 1) -= (с, + c₂ + c₃ + c₆)N - (c₂ + c, + c_e).

Зважаючи на те, що при обчисленні кількості виконуваних алгоритмом операцій константами можна знехтувати, то мож­на зробити висновок, що для нашого алгоритму вона станови­тиме — N.

У другому випадку треба переставити місцями всі елементи масиву. Тому обчислення слід вести за формулою:

T(N) = c₁N + c₂(N-l) + c₃{N-l) + c₄± £ '-+

+ c₅^N{N₂'¹Kc₆(N-l) = c_lN + c₂(N-l) ₊ c₃(N-l) ₊ N²+N-2 N²-N ,„ ,. (с. c.V_Tl

^{+ c}< 2— ♦v-j^^-i)-^*]» ⁺

+ f с, + c₂ +c₃ +|-_|. _{+ Ce} W -(e, +C, +c< +c,\

Ми отримали квадратичний вираз для обчислення часу ви­конання алгоритму в найгіршому випадку. Оскільки при вели-

16

них значениях N можна вважати, що N значно менше за N^z i,

як відомо, константами можна знехтувати, то кількість обчис-

лювальних дій - N².

N Для останнього випадку зсув треба буде виконати для — еле-

2

ментів масиву (кроки 4 і 5), але при цьому все одно перегляну-

ти всі елементи масиву. Визначити час можна за формулою: T(N) = c_lN + c₂{N-l) + c_a{N-l) + c_t(^{2 + N}^^N~¹K

+k+c₂ + c₃+^--|--c_e W-

^С4

Це доводить, що i в середньому випадку час квадратично за-лежить від N, тобто кількість обчислювальних дій « N².

Отже, бачимо, що час роботи в найгіршому і найкращому випадках дуже відрізняється один від одного. Але найчастіше нас цікавитиме саме час роботи в найгіршому випадку. Чому саме так? Спробуємо відповісти на це запитання таким чином: на це є три причини.

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

2. На практиці «погані» вхідні дані зустрічаються частіше, ніж «гарні».

3. У середньому випадку час роботи алгоритму може бути дуже близьким до часу роботи в найгіршому випадку.

Як позначати отриману характеристику ефективності робо­ти алгоритму? Аналіз часу роботи алгоритму упорядкування за зростанням N елементів одновимірного масиву методом вклю­чения базувався на декількох спрощеннях. У формулах, виве-дених для обчислення кількості операцій, виконуваних алго­ритмом, ми знехтували членами менших порядків (лінійними) та коефіцієнтом при N². Робимо висновок, що швидкість росту часу роботи алгоритму є квадратичною. Це записується так: 0(N²).

Зрозуміло, що алгоритм, для якого час виконання визна-чається як 0(N²), мае переваги перед алгоритмом, час виконан­ня якого 0(N³). Чим більшою буде кількість вхідних даних, тим відчутнішими будуть ці переваги.

Заслуговуе на увагу й аналіз алгоритмів типу «розділяй і во-лодарюй». Підрахунок кроків таких алгоритмів не дуже прос-тий. Він залежить від рекурсивних викликів, від підготовчих та завершальних дій.

17

Як приклад розглянемо рекурсивный алгоритм обчислення значения факторіала:

1. Factorial(N);

2. if N = 1

3. then Factorial := 1

4. else Factorial := N * Factorial(N - 1);

Введемо такі позначення: a - кількість підзадач, на які поді-ляється наша задача; b - коефіцієнт, який визначає, у скільки ра-зів підзадача менша за задачу; T(N/b) - час виконання підзада-чі; D(N) - час, необхідний для поділу задачі на підзадачі; C(N) -час, необхідний на об'єднання отриманих розв'язків підзадач у кінцевий результат. Таким чином, формула для обчислення за-гального часу виконання рекурсивного алгоритму буде такою:

0(N) = a!7i— + D(N) + C{N).