Решение рекуррентного отношения для рекурсивной функции - PullRequest
Новая
       50

Решение рекуррентного отношения для рекурсивной функции

0 голосов
/ 02 июня 2019

enter image description here Мне нужно создать и решить рекуррентное отношение для анализа наихудшего случая для следующего псевдокода. Я рассчитываю добавление чисел (не считая счетчика цикла for) в качестве основной операции. Я предполагаю, что п = 2 ^ к.

Вот мой прогресс ... Базовый вариант: T (n <= 4) = 1 </p>

W (n) = W (2 ^ k) = добавления для вычисления ответа + добавления в следующей рекурсии + добавление в цикл for W (2 ^ k) = 2 + W (2 ^ (k-2)) + (2 ^ k) - 2 = W (2 ^ (k-2)) + (2 ^ k)

Я использую обратную подстановку и получаю следующее рекуррентное соотношение ...

для j-го рекурсивного вызова W (2 ^ k) = W (2 ^ (k-2j)) + (2 ^ k) + сумма (t = 1, j, 2 ^ (k-2 (t-1)))

Я знаю, что могу упростить это, потому что я беру W (2 ^ (k-2j)) = W (4) и решаю для j, чтобы увидеть, сколько рекурсивных шагов делает код. В этом случае j = (k / 2) - 1. Уменьшение повторения дает мне ...

W (2 ^ k) = 1 + (2 ^ k) + сумма (t = 1, j, 2 ^ (k-2 (t-1))).

Сокращение суммы дает мне ...

W (2 ^ k) = 1 + (2 ^ k) + (2 ^ k) * (2 ^ 2) * сумма (t = 1, j, 2 ^ (- 2t)) или

W (n) = 1 + n + 4n * сумма (t = 1, j, 2 ^ (- 2t))

Что я не могу упростить, так это суммирование. В лекциях у нас может быть суммирование суммы (i = 1, n, 2 ^ i), которая была бы 2 ^ (n + 1) -1, но эта отличается. 

int function calc(int n) {
   int num,answer;
   if(n<=4) {return n+10;}
   else {
     num=calc(n/4);
     answer=(num+num+10);
     for(int i=2;i<=n-1;i++) {
         answer=answer+answer;
     }
     return answer;
  }
}

Любая помощь будет оценена. Это назначение должно быть сегодня вечером. Спасибо

Ответы [ 2 ]

1 голос
/ 02 июня 2019

временная сложность задачи T(n) = T(n/4) + n.Термин n может означать \Theta(n).Следовательно, T(n) = n + n/4 + n/4^2 + ... + n/(4^log_4(n)) = n(1 + 1/4 + ... + 1/n) = \Theta(n).Обратите внимание, что lim_{n\to \infty} 1 + 1/4 + ... + 1/4^log_4(n) = 4/3 это постоянное число.

0 голосов
/ 02 июня 2019
  • T (n) = T (2 ^ k) // по предположению
  • T (n) = T (n / 4) + n // - рекуррентное соотношение
  • T (2 ^ k) = T (2 ^ (k-2)) + (2 ^ k) // переписать
  • T (2 ^ k) = T (2 ^ (k-2j)) + (2 ^ k) * SUM (i = 0; j-1; (1/4) ^ i) // - отношение для итерации j
  • T (4) = T (2 ^ (k-2j)) = 1 // когда рекурсия заканчивается, базовый случай достигнут, только 1 сложение
  • 2 ^ 2 = 2 ^ (k-2j) // переписать и удалить T
  • 2 = k-2j // удалить общее основание
  • j = (k / 2) -1 // решить для j-й итерации
  • Примечание: не может быть десятичным для итерации, поэтому j = CEILING ((k / 2) -1)
  • СУММА (i = 0; j-1; (1/4) ^ i) = (1- (1/4) ^ j) / (1- (1/ 4))
  • Геометрические суммы и доказательства преобразования приведены выше, см. Вики-ссылку ниже
  • Подставляя j в CEILING ((k / 2) -1), сумма равна ...
  • СУММА = (1- (1/4) ^ (ПОТОЛОК ((k / 2) -1))) / (1- (1/4))
  • Наконец, T (2^ k) = 1 + (2 ^ k) * SUM
  • В терминах ввода n, T (n) = 1 + (n * SUM)
  • Эта формула подходит для всехk> = 1

Проверка нескольких значений ...

  • k = 1, T (2) = 1 + (2 * 0) = 1 // мы знаем, что это правда, потому что T (2) является базойcase
  • k = 2, T (4) = 1 + (4 * 0) = 1 // мы знаем, что это правда, потому что T (4) является базовым случаем
  • k = 3, T (8) = 1 + (8 * 1) = 9 // по формуле повторения, T (8) = T (2) + 8 = 9, верно
  • k = 4, T (16)= 1 + (16 * 1) = 17 // по формуле повторения, T (16) = T (4) + 16 = 17, истина
  • k = 5, T (32) = 1 + (32* 1.25) = 41 // по формуле повторения, T (32) = T (8) + 32, T (8) = 9, 32 + 9 = 41 true

Для геометрических сумм https://en.wikipedia.org/wiki/Geometric_series

...