Решение рекуррентных ситуаций методом подстановки

Итак, в настоящее время я прохожу курс «Алгоритмы», и у меня возникла проблема с повторениями и получением времени выполнения. Мне было интересно, может ли кто-нибудь объяснить мне с точки зрения непрофессионала, как решить с помощью метода подстановки.

Вопрос из книги: Алгоритм B решает задачи размера n, рекурсивно решая две подзадачи размера n − 1, а затем объединяя решения за постоянное время.

Что привело меня к следующему повторению: T(n)=2T(n-1)+O(1). Затем я придумал O(1)=1. Что дало мне следующее: T(n)=2T(n-1)+1

Вот моя попытка решить это

T(n)=2T(n-1)+1
=2(2T(n-2)+1)+1=4T(n-2)+3
=4(2T(n-3)+1)+3=8T(n-3)+7
=8(2T(n-4)+1)+7=16T(n-4)+15
=16(2T(n-5)+1)+15=32T(n-5)+31
=32T(2T(n-6)+1)+31=64T(n-6)+63

Если я все делаю правильно, как мне продолжать получать время работы? Может ли кто-нибудь объяснить на непрофессиональном уровне, как использовать метод подстановки?


recurrence algorithm
person user3561871    schedule 16.02.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы близки, но вы можете отформатировать свою обратную замену, чтобы она имела немного больше смысла:

T(n)
=2^1T(n-1)+(2^1-1)
=2^2T(n-2)+(2^2-1)
=2^3T(n-3)+(2^3-1)
=2^4T(n-4)+(2^4-1)
=2^5T(n-5)+(2^5-1)
=2^6T(n-6)+(2^6-1)
...

Здесь вы можете увидеть закономерность, когда n приближается к 0. Это становится чем-то вроде 2^n + 2^n - 1, а в нотации Big-O — O(2^n).

Некоторое понимание, которое у меня было, может помочь вам с другими отношениями повторения: повторение происходит n раз, и каждая итерация умножается на 2. Звучит примерно как 2^n!

person kevchoi    schedule 16.02.2016
comment
Благодарю вас! Так что я был на правильном пути. Я заметил, что он удваивает каждый шаг, поэтому я подумал, что Big-O равен O (2 ^ n). У меня есть еще один вопрос, если вы не возражаете, если я спрошу, когда вы используете основную теорему против метода подстановки? - person user3561871; 16.02.2016
comment
Вы можете использовать основную теорему только для рекуррентных отношений определенной формы, см. en.wikipedia.org/wiki/ Основная_теорема. Лично я вижу, можно ли решить рекуррентное соотношение даже с помощью основной теоремы. Если он не той формы, я использую метод подстановки. - person kevchoi; 16.02.2016