1.2.4. Оцінювання складності алгоритму під час застосування кожної стратегії
Складність алгоритму «розділяй і владарюй» обчислюється за допомогою основної теореми про рекурентні співвідношення:
T(n) = aT(n/b) + f(n)
Тут:
n - обсяг вхідних даних.
a - кількість підзадач у рекурсії.
n/b - Розмір кожної подзадачи. Передбачається, що всі завдання мають однаковий розмір.
f(n) - оцінка виконаної роботи поза рекурсивними викликами. Також вона включає обчислювальну вартість поділу на підзадачі та об'єднання рішень цих підзадач.
Спробуємо знайти тимчасову складність рекурсивного завдання.
Як приклад візьмемо сортування злиттям. Рівняння набуває наступного вигляду:
T(n) = aT(n/b) + f(n) = 2T(n/2) + O(n)
Тут:
a = 2 (на кожному кроці завдання ділиться на дві підзадачі);
n/b = n/2 (розмір кожної підзавдання - половина вихідної);
f(n) = витрачений час на розподіл завдання на підзавдання та їхнє наступне об'єднання;
T(n/2) = O(n log n) (щоб зрозуміти цей вираз, прочитайте цю статтю).
Зрештою T(n) = 2T(n log n) + O(n) ≈ O(n log n)
Рекурентні вирази використовуються, зокрема, для визначення складності рекурсивних обчислень. Наприклад, при спробі вичислити числа Фібоначчі за рекурсивною схемою F(i) = F(i - 1) + F(i - 2), при N >= 1; F(0) = 0; F(1) = 1. текст програми буде приблизно таким:
Кількість рекурсивних викликів при обчисленні значення F(N) за такою схемою може бути отримана з рішення рекурентного виразу TN = TN-1 + TN-2, при N>=1; T0 = 1; T1 = 1, де
TN приблизно рівний ФN, де Ф~1.618 - золота пропорція, тобто приведена вище програма зажадає експоненціальних тимчасових витрат на обчислення.
Динамічне програмування може мати високу обчислювальну складність, особливо якщо вихідна задача дуже складна і може бути розбита на безліч підзадач.
1.3. Моделі обчислень
Модель обчислення в інформатиці, а особливо у теорії обчислюваності та теорії складності обчислень — це визначення множин допустимих операцій, що використовуються при обчисленні, та їх відповідні витрати. Вона використовується у обчисленні складності алгоритму або проблеми, для вирішення якої вона була створена. Це допомагає дослідити продуктивність алгоритмів незалежно від варіантів, специфічних для конкретних імплементацій та конкретних технологій.
Деякі приклади моделей обчислення:
Машина Тюрінга
Скінченні автомати
Рекурсивні функції
Лямбда-числення
Комбінаторна логіка
Клітинний автомат
Абстрактні переписні системи
Взаємодія мереж
Мережа процесів Кана
У галузі фази життєвого циклу програми аналізу алгоритмів треба зазначити обчислювальну модель у термінах дозволених «примітивних операцій», які мають вартість одиниці або просто «операції з вартістю один». Найпоширенішим прикладом є RAM-машина, яка має вартість одиниці для доступу до читання та запису в усіх комірках пам'яті. У цьому відношенні він відрізняється від вищезгаданої моделі машини Тюрінга.
У розробці, керованій моделями, модель розрахунку пояснює, що поведінка всієї системи є результатом поведінки кожного з її компонентів.
Ключовий момент, про який часто забувають, полягає в тому, що зазначені нижні межі для задач часто ставляться для моделі обчислення, яка більш обмежена, ніж набір операцій, які можна використовувати на практиці. Тому можуть існувати алгоритми, які будуть працювати швидше, ніж можна буде вважати можливим.
Існує безліч моделей обчислень, що відрізняються в наборі допустимих операцій та вартістю їх обчислень. Їх можна розділити на такі загальні категорії як автомат та їй еквівалентні (наприклад, Лямбда-числення еквівалентне машини Тюрінга). Вони використовуються в доведеннях обчислюваності та верхньої межі обчислювальної складності алгоритмів. Також існують моделі дерева рішень, що використовуються у доведеннях нижніх меж обчислюваної складності алгоритмічних задач.