Часова ефективність алгоритмів. Рекурентні рівняння. Лабораторна робота з Алгоритми та моделі обчислень. Робота № 100759

Часова ефективність алгоритмів. Рекурентні рівняння

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

ІКТА

Факультет:

КН

Кафедра:

Спеціалізовані комп’ютерні системи

Інформація про роботу

Рік:

2024

Тип роботи:

Лабораторна робота

Предмет:

Алгоритми та моделі обчислень

Завантажити

Частина тексту файла (без зображень, графіків і формул):

ЛАБОРАТОРНА РОБОТА №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. Висновок: на цій лабораторній роботі я визначила час виконання фрагменту програми та розв’язала рекурентне рівняння. Закріпила отримані теоретичні знання та практичні навички при виконанні даної лабораторної роботи.

Лабораторна робота Алгоритми та моделі обчислень

ol-bo

15.09.2024 14:50

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись