Что такое + n для

Question

Для этого алгоритма

Bugs(n)
    if n = 0 generate 5 bugs
    else 
        Bugs(n-2);
        for i ← 1 to n
            generate 1 bug
        Bugs(n-2);

Отношение повторения: T(n) = 2T(n-2) + n, T(0) = 5

Почему существует a +n?Это потому, что они только один для цикла, поэтому если их будет два для цикла, это будет + n^2?

Answer 1

Хорошо, посмотрите, что он делает для случая n! = 0:

• Он вызывает ошибки (n-2), поэтому T(n-2) для этой части
• Он генерирует n ошибок - поэтому n при условии, что «сгенерировать 1 ошибку» постоянен
• Он вызывает ошибки (n-2) - так что T(n-2) again

Всего: 2T(n-2) + n