Обычно при анализе программ мы начинаем с рекурсивного определения программы и пытаемся вычислить замкнутую форму или функцию для рекурсивного определения, а затем решаем ее временную сложность. Здесь мы делаем наоборот, мы начинаем с закрытой формы или функции и меняем ее на рекурсивное определение.
Ниже у нас есть проблема или функция, которую мы хотим преобразовать в рекурсивное определение.
f(n) = 2^n + 1
Базовый вариант - это завершающий случай в рекурсии, который не использует рекурсию для получения ответа. Базовый случай здесь - когда n = 0, чтобы получить f (0) = 2.
Базовый случай: попробуйте найти n = 0
f(0) = 2⁰ + 1
= 1 + 1
= 2
Рекурсивный случай - это случай, когда функция определяет сама себя. Здесь мы пытаемся создать рекурсивный случай для нашей функции f (n) = 2 ^ n + 1. Если f (n) = 2 ^ (n) +1, то f (n + 1) = 2 ^ (n + 1) +1.
Рекурсивный случай: попробуйте решить f (n)
f(n+1) = 2^(n+1) + 1
= 2 * 2^n + 1
= (2 * 2^n )+ 1
= (2^n + 2^n ) + 1
= 2 ^n + 2^n + 1
= 2 ^n + 2^n + 1 + 0
= 2 ^n + 2^n + 1 + 1–1
= 2 ^n + 1+ 2^n + 1 –1
= (2 ^n + 1)+ (2^n + 1) –1
= f(n) + f(n) — 1
f(n+1) = f(n) + f(n) — 1
f(n+1 -1 ) = f(n)
f(n + 1–1) = f(n-1) + f(n-1) — 1
f(n) = f(n-1) + f(n-1) — 1
f(n) = 2f(n-1) — 1
Вывод:
Рекурсивное определение для f (n) = 2 ^ n + 1 приведено ниже.
f(0) = 2
f(n) = 2f(n-1) — 1
Эта временная сложность функции, конечно же, O (2 ^ n)
Если вы хотите узнать больше об Анализ алгоритмов, вы можете пройти мой онлайн-курс здесь. У меня также есть курс на Udemy.com под названием Recurrence Relation Made Easy, где я помогаю студентам понять, как решать повторяющиеся отношения и асимптотические термины, такие как Big-O, Big Omega и Theta. Вы можете посмотреть мой канал на YouTube с видео, где я решаю рекуррентные отношения и выполняю анализ алгоритмов кода, который любой может проверить бесплатно!
Спасибо за прочтение этой статьи, надеюсь, она будет вам полезна! Продолжайте учиться, и если вы хотите больше видео по информатике, программированию и анализу алгоритмов, посетите и подпишитесь на мои каналы YouTube (randerson112358 и compsci112358)
Ознакомьтесь со следующими материалами / видео по информатике, анализу алгоритмов, программированию и логике:
Канал YouTube:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ
compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA
Веб-сайт:
http://everythingcomputerscience.com/
Видеоуроки по взаимосвязи повторяемости:
https://www.udemy.com/recurrence-relation-made-easy/
Видеоурок по анализу алгоритмов:
https://www.udemy.com/algorithm-analysis/
Twitter:
https://twitter.com/CsEverything
"YouTube канал:"
Веб-сайт по информатике:
Видео Udemy по алгоритмическому анализу:
