ВИЗНАЧЕННЯ ЕФЕКТИВНОСТІ І СКЛАДНОСТІ ДОСЛІДОВАНИХ АЛГОРИТМІВ

Мета роботи: навчитися обчислювати ефективність та складність досліджуваного алгоритму.

Завдання роботи: опанувати навички визначення ефективності та складності досліджуваних алгоритмів.

  1. вивчити опис лабораторної роботи;
  2. за завданням, даним викладачем, розробити алгоритм розв'язання задачі;
  3. дослідити програму, складену будь-якою мовою;
  4. вирішити завдання;
  5. оформити звіт.

Теорія складності алгоритмів

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

Ефективність алгоритму тимчасова складність у найгіршому випадку O(f(n)) або просто f(n). Функція від n f (n) дорівнює максимальному числу кроків, що виконуються алгоритмом і має порядок зростання O (f (n)), причому максимум береться за всіма вхідними даними довжини n. Існує константа c така, що для досить великих n величина c f (n) є верхньою межею кількості кроків, що виконуються алгоритмом для будь-яких вхідних даних довжини n. Аналіз рекурсивних програм значно складніше звичайних, оскільки часто потрібно вирішувати диференціальні рівняння. Для аналізу необхідно застосовувати методи схожі на методи розв'язання диференціальних рівнянь. При аналізі рекурсивних процедур складаються рекурентні співвідношення, які одержують виходячи зі структури рекурсивного алгоритму, що відображають характер рекурсивного виклику алгоритму та залежать.від величини вхідних даних

Рішення рекурентних співвідношень

Існують 3 способи вирішення рекурентних співвідношень:

  1. Знаходиться функція f ( n ) , яка мажорує T ( n ) всім значень n , тобто . всім n виконується нерівність T(n)f(n). Іноді тільки ймовірно визначається вид функції f (n), що залежить від деяких невизначених параметрів. Далі підбираються такі параметри, що всім n виконуватиметься T ( n ) f ( n ) .
  2. Послідовно підставляються в рекурентне співвідношення залежності T ( m ) , де m n , так, щоб з правої частини були виключені всі T ( m ) з m , залишивши тільки T (1) . Але оскільки T (1) завжди є константою, то вийде під кінець залежність від констант і n.
  3. Використання загальних рішень.

Оцінка рішень рекурентних співвідношень

Розглянемо приклад процедури-функції mergesort сортування злиттям, вхідні дані якої є список елементів довжиною n, а вихідні це відсортований список. Ця функція також використовує процедуру злиття merge , вхідні дані якої є два відсортованих списку L 1 і L 2 . Ця процедура переглядає ці списки поелементно, починаючи з великих. На кожному кроці найбільший елемент із двох порівнюваних видаляється зі свого списку і поміщається у вихідні дані. Виходить цим єдиний відсортований список, що містить всі елементи L 1 і L 2 . Процедура на списках merge, довжиною n/2 виконується за час порядку O(n).

function mergesort (L: LIST; n: integer): LIST;

if n=1 then return(L)

розбиття L на дві частини L 1 і L 2 кожна довжиною n /2;

return(merge(mergesort(L1, n/2),(mergesort(L2, n/2))));

Нехай T(n) - час виконання процедуриmergesort у найгіршому випадку. Аналізуючи текст програми, запишемо рекурентну нерівність, яка обмежує зверху T(n):

У даній нерівності c 1 є кількість кроків виконуваних алгоритмом над списком L довжиною 1. Час роботи процедури можна розбити на дві частини, якщо n >1 . Перша частина складається з: 1) перевірки n <>1, 2) розбивки L , на дві рівні частини і 3) виклику процедури merge . Ці три операції вимагають або фіксований час для виконання першої частини або пропорційного n для другої та третьої. Отже, можна вибрати таку константу c 2 яка створюватиме обмеження для виконання даної частини процедури рівне c 2 * n . Друга частина процедури mergesort складається з двох рекурсивних викликів цієї процедури для списків довжини n/2, які вимагатимуть час 2 T (n/2). Так була отримана друга нерівність.

Формулу верхньої межі в замкнутій формі можна отримати, якщо n є ступенем числа 2 . При виконанні цієї умови T(n) можна оцінити для будь-яких n. Іншими словами, якщо n лежить у проміжку, то значення T(n) розташовується між T(2i)… T(2i+1). Неважко помітити, що вираз 2 T (n) можна замінити на T((n+1)/2)+ T((n-1)/2) для непарних n>1. Таким чином, можна знайти рішення рекурентного співвідношення в замкнутій формі для будь-яких n. Замкнена форма - це вид функції T(n), що не включає ніяких виразів T(m) для mn.

Зробимо оцінку рекурентного співвідношення (7.1).

Замінимо в цьому співвідношенні n на n/2 і отримаємо

Підставимо праву частину (7. 2) у (7. 1)

Замінюючи аналогічним чином (7. 1) n на n /4 , отримуємо оцінку для T ( n /4) : T ( n /4)  2 T ( n /8)+ c 2* n /4 . Підставимо цю оцінку в (7.3) та отримаємо такевираз:

Проаналізувавши характер зміни T (n) перетворимо (7.1) на вигляд:

Припустимо, що тоді при i = k у правій частині (7.5) знаходиться T (1) :

Оскільки , то ,а T (1)  c 1 , то (7.6) можна перетворити

Нерівність (7.7) демонструє верхню межу для T(n), а порядок зростання T(n) не більше O(n logn).

Завдання щодо варіантів:

Для свого варіанта стовпець A , вибрати рекурентне рівняння і значення T (1) . Необхідно вирішити це рекурентне співвідношення і визначити ефективність алгоритму, описаного функцією T (n).