МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ «ЛЬВІВСЬКА ПОЛІТЕХНІКА» Інститут ІКТА Кафедра СКС ЗВІТ Лабораторна робота №1 з курсу “Алгоритми та моделі обчислень” ЛАБОРАТОРНА РОБОТА №1 Тема: Часова ефективність алгоритмів. Рекурентні рівняння Мета роботи: Визначення часу виконання для заданих фрагментів програм та для заданих рекурентних співвідношень. Завдання 1 (b) Фрагмент коду програми: Виконання: Цей фрагмент коду складається з циклу while, який виконується n разів, тобто його час виконання залежить від значення n. Час виконання цього фрагменту коду можна визначити за допомогою формули: T(n) = 7n + 5 Блок-схема: Завдання 2 b) Рекурентне рівняння: ?(?)= 1, ?=0; ?(?)= 2?(?−1)+1, ?≥1. Щоб визначити складність алгоритму, можна скористатися методом підстановки. Рекурсивно розв'язуючи рівняння, отримаємо: T(n) = 2T(n-1) + 1 T(n) = 2[2T(n-2) + 1] + 1 T(n) = 2^2T(n-2) + 2 + 1 T(n) = 2^2[2T(n-3) + 1] + 2 + 1 T(n) = 2^3T(n-3) + 2^2 + 2 + 1 Після k кроків отримаємо: T(n) = 2^kT(n-k) + (2^{k-1} + 2^{k-2} + \dots + 2^1 + 1) Якщо T(0) = 1, то n-k = 0 і T(n-k) = 1. Отже, при n кроках (коли n - k = 0), отримуємо: T(n) = 2^nT(0) + 1 + 2 + 2^2 + … + 2^{k-1} = 2^n * 1 + 2^k – 1 = 2^n + 2^n -1 = 2^{n+1} – 1. Відповідь: T(n) = 2^{n+1} – 1. Висновок: на цій лабораторній роботі я визначила час виконання фрагменту програми та розв’язала рекурентне рівняння. Закріпила отримані теоретичні знання та практичні навички при виконанні даної лабораторної роботи.