Ефективність алгоритмів

Припустимо, швидкодія комп'ютера та об'єм його пам'яті можна збільшувати до нескінченності. Чи була би тоді необхідність у вивченні алгоритмів? Так, але тільки для того, щоб продемонструвати, що метод розв'язку має скінченний час роботи і що він дає правильну відповідь. Якщо б комп'ютери були необмежено швидкими, підійшов би довільний коректний метод рішення задачі. Звісно, тоді найчастіше обирався би метод, який найлегше реалізувати.

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

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

Як зазначалось вище, в цьому розділі центральну роль буде присвячено задачі сортування. Перший алгоритм, який буде розглядатись - сортування включенням, для своєї роботи вимагає часу, кількість якого оцінюється як c₁n², де n - розмір вхідних даних (кількість елементів у послідовності для сортування), сі - деяка стала. Цей вираз вказує на те, як залежить час роботи алгоритму від об'єму вхідних даних. У випадку сортування включенням ця залежність є квадратичною. Другий алгоритм - сортування злиттям - потребує часу, кількість якого оцінюється як C2n*log2n. Зазвичай константа сортування включенням менше константи сортування злиттям, тобто ci<c₂, але як ми пересвідчимось у наступних темах, ці константи не відіграють ролі у порівнянні швидкодії різних алгоритмів. Адже зрозуміло, що функція n² зростає швидше зі збільшенням n, аніж функція nlog₂n. І для деякого значення n = n₀ буде досягнуто такий момент, коли вплив різниці констант перестане мати значення і надалі функція c₂nlog₂n буде менша за c₁n² для будь-яких n > n₀.

Для демонстрації цього розглянемо два комп'ютери - А та Б. Комп'ютер А більш швидкий і на ньому працює алгоритм сортування, а комп'ютер Б більш повільний і на ньому працює алгоритм сортування методом злиття. Обидва комп'ютери повинні виконати сортування множини, яка складається з мільйона чисел. Припустимо, що комп'ютер А виконує мільярд операцій в секунду, а комп'ютер Б - лише десять мільйонів, тобто А працює в 100 разів швидше за Б. Щоб різниця стала більш відчутною, припустимо що код методу включення написаний найкращим програмістом в світі із використанням команд процесору, і для сортування n чисел за цим алгоритмом потрібно виконати 2n² операцій (тобто c₁=2). Сортування методом злиття на комп'ютері Б написано програмістом початківцем із використанням мови високого рівня і отриманий код потребує 50nlog₂n операцій (тобто c₂=50). Таким чином для сортування мільйона чисел комп'ютеру А буде потрібно

а комп'ютеру Б –

Тож, використання коду, час роботи якого зростає повільніше, навіть при поганому комп'ютері та поганому компіляторі потребує на порядок менше процесорного часу! Для сортування 10 мільйонів чисел перевага сортування злиттям стає ще більш відчутною: якщо сортування включенням потребує для такої задачі приблизно 2,3 дня, то для сортування злиттям - менше 20 хвилин. Загальне правило таке: чим більша кількість елементів для сортування, тим помітніше перевага сортування злиттям.

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

Золоте правило розробників алгоритмів

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

Вхід: 2 цілих n-розрядних числа x та y

Вихід: добуток чисел xy

Розглянемо приклад для чисел x = 5678 та y = 1234. Результат відомого з дитинства методу множення в стовпчик буде виглядати наступним чином (рис. 2.1):

Рис. 2.1 – Процедура множення

Легко помітити, що елементарні операції, які тут використовуються, це - множення та додавання однорозрядних чисел. Припустивши, що операція множення займає більше часу аніж операція додавання для однієї пари чисел, оцінимо кількість таких елементарних операцій. Всі вони виконується в області, яка вище позначена сірим кольором. В даному прикладі кількість елементарних операцій добутку становитиме 16 = 4², а в загальному випадку становитиме n². Тож, кількість операцій для добутку двох цілих n-розрядних чисел методом множення у стовпчик оцінюється як cn², де с - деяка стала.

Проте чи можемо ми покращити цей результат, отримавши метод добутку чисел, який буде працювати швидше? Щоб мотивувати себе для пошуку такого методу, наведемо цитату з книги «Розробка та аналіз комп'ютерних алгоритмів» (Аго, Гопкрофт, Ульман, 1974): «Можливо найбільш важливим принципом для гарного розробника алгоритмів є відмова від того, щоб бути задоволеним результатом». Слідуючи цьому правилу, розглянемо ще раз детальніше природу об'єктів задачі добутку чисел.

За умовою на вхід подається два n-розрядних числа. Припустимо ми розіб'ємо кожне число навпіл, отримавши, так звані, верхнє та нижнє півслова. Тобто, можна записати x = 10^{n 2} a + b та y = 10^{n 2} c + d , де a, b, c, d - цілі n/2-розрядні числа. Тоді добуток xy можна представити так:

xy =(10^n/2 a + b)- (10^n/2 c + d) = 10ⁿac +10^n/2 (ad + bc)+ bd. (2.1)

Таким чином ми природно підійшли до рекурсивного методу обчислення добутку двох цілих чисел, який зводить обрахунок добутку двох n-розрядних чисел до обрахунку чотирьох добутків n/2-розрядних чисел. Спробуємо з'ясувати, чи покращиться таким чином швидкість добутку двох чисел. Кожне з чисел a, b, c, d мають n/2 розрядів, а відтак добуток будь-якої їх пари (якщо використовувати для нього старий алгоритм множення у стовпчик) займатиме c(n/2)² операцій, тобто cn²/4. Чотири таких добутки в сумі знову дадуть початковий результат: 4-cn /4 = cn . Отже, виграш за часом не було отримано.

Невже не можливо покращити результат роботи методу множення чисел у стовпчик? Насправді, можливо і відповіддю на це питання є метод множення Карацуби (1960). Якщо подивитись на формулу (2.1), то помітимо, що насправді важливими є не чотири до, а три: ac, bd та (ad + bc), тобто елементи ad та bc нас не цікавлять самі по собі, а лише їх сума. Чи можна отримати їх суму перемноживши лише два числа? Так:

(a + b)(c + d) = ac + ad + bc + bd = (ad + bc) + sic + bd

aid + bc = (a + b)(c + d) - ac - bd (2.2)

Таким чином, суму (s + bc) можна отримати з добутку двох n/2-розрядних числа (можливо, n/2 + 1) (a+b) та (c+d), а також добутків ac та bd, які ми вже маємо. І, отже, кількість рекурсивних викликів скоротились з чотирьох до трьох. Аналіз швидкості методу множення приводить до оцінки 3n¹⁰⁸²³ » Зn¹¹⁵⁸⁵ .