Міністерство освіти і науки України Тернопільський національний технічний університет імені Івана Пулюя Кафедра комп’ютерних наук Контрольна робота 6 з дисципліни “Теорія алгоритмів” Оцінити складність алгоритму Евкліда. Для оцінки часу виконання алгоритму знаходження найбільшого спільного дільника двох чисел покладемо, що час виконання кожного елементарного оператора однаковий і рівний одній умовній одиниці. Беручи до уваги вище подані припущення оцінимо час виконання такого алгоритму визначивши необхідну кількість операцій для його виконання. Отже, необхідна кількість операцій визначається з робочої функції алгоритму, яка матиме вигляд:
, де n — залежить від заданих чисел. Оцінити складність алгоритму роботи елементарної системи керування. Можемо оцінити час виконання циклу керування алгоритму роботи елементарної системи керування визначивши кількість виконуваних операцій циклу. Необхідну кількість виконуваних операцій циклу визначимо з робочої функції алгоритму, яка буде мати наступний вигляд
, де n — кількість циклів роботи елементарної системи керування. Оцінити складність рекурсивного алгоритму розв'язування звичайного диференціяльного рівняння другого порядку з постійними коефіцієнтами. Можемо оцінити час розв’язування звичайного диференціального рівняння першого порядку визначивши необхідну кількість операцій. Необхідну кількість операцій визначимо з робочої функції алгоритму, яка буде мати наступний вигляд:
, де n = 2. Отже, в даному випадку, складність такого алгоритму буде 5 умовних одиниць. Порівняти складність трансверсального та рекурсивного алгоритмів розв'язування звичайного диференціяльного рівняння другого порядку. Робоча функція рекурсивного алгоритму розв'язування звичайного диференціяльного рівняння другого порядку має наступний вигляд:
, де n = 2. Робоча функція трансверсального алгоритму розв'язування звичайного диференціяльного рівняння другого порядку має такий вигляд:
, де n = 2. Отже, на основі даних робочих функцій можемо зробити висновок, що трансверсальний алгоритм є менш складним, адже виконується меншу кількість часу.