Метод развертывания для: T (n) = 1, когда n = 0 и 2T (n-1) + 1

Question

Для

• T (n) = 1, когда n = 0
• T (n) = 2T (n-1) + 1, в противном случае

Я знаю, что мы должны искать шаблоны и понимать проблему до тех пор, пока не начнем преобразовывать уравнения с различными переменными.Однако, как только я доберусь туда, я не пойму, как это делается и почему определенные действия сделаны.

Моя проблема, в частности, заключается в том, что мы заменим i на n при 2 ⁱ · T (n-1).Тем не менее, полное объяснение было бы также полезно!

Answer 1

Это так же, как 99999 ₁₀ равно 100000 ₁₀ - 1, 11111 ₂ равно 100000 ₂ - 1.

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

• T (0) = 1
• T (1) =1 << 1 + 1 = 3 </li>
• T (2) = 3 << 1 + 1 = 7 </li>
• ...

Здесь << - этоОператор «сдвига влево» для двоичных чисел, который эквивалентен умножению на 2. Этот оператор довольно распространен во многих языках программирования.Это помогает показать, что вы просто добавляете 1 бит на каждом этапе пути.Возвращаясь к первому утверждению, <em>n последовательные биты равны 2 ^{n + 1} - 1.

В объяснении в вашем вопросе просто используется i в качестве счетчика, который работает от 1 до n .Это не часть уравнения, за исключением счетчика шагов.На последнем шаге i = n , следовательно, конверсия, в которой вы можете быть запутаны.