Метод повторения итераций решить

Question

Привет, у меня есть это повторение: как решить? а) Решите следующее повторение, используя метод итерации, и дайте асимптотическое время выполнения: T(0)=0 и T(n)=10 +T(n-1), для n ≥ 1

Answer 1

Вы можете использовать метод динамического программирования для итеративного решения проблемы:

define results[n+1];
results[0] = 0;

for (i = 1; i < n + 1 ) {
      set  results[i] to 10 + results[i-1] 
}

Tn = results[n];

Время работы по вышеуказанному алгоритму будет n.