Решая рецидивы с использованием метода замещения

Question

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

Вопрос из книги: Алгоритм 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 

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

Answer 1

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

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!