Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Часова ефективність алгоритмів. Рекурентні рівняння
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
КН
Кафедра:
Спеціалізовані комп’ютерні системи
Інформація про роботу
Рік:
2023
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та моделі обчислень
Частина тексту файла (без зображень, графіків і формул):
ЛАБОРАТОРНА РОБОТА №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.
Висновок: на цій лабораторній роботі я визначила час виконання фрагменту програми та розв’язала рекурентне рівняння. Закріпила отримані теоретичні знання та практичні навички при виконанні даної лабораторної роботи.
15.09.2024 14:09-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора