Как определить время выполнения T (n) для данной рекурсивной функции?

Question

Как определить формулу повторения T (n) для следующей функции?

if(N == 0)
  return 1;

s = 0;

x = function(N/3);

for(i = 1; i <= N; i++){
  s += x;
}

return s;

Answer 1

Вы можете использовать основную теорему:

T (n) = a * T (n / b) + C * n ^ k (с a, b, C> 0, k в N).

вариант 1: a T (n) находится в Θ (n ^ k)

вариант 2: a = b ^ k -> T (n) находится в Θ (n ^ k * log (n))

вариант 3: a> b ^ k -> T (n) находится в Θ (n ^ logb a)

В вашем случае T (n) = 1 * T (n / 3) + С * n ^ 1.

a = 1, b = 3, k = 1 -> T (n) в Θ (n).

Answer 2

Вы можете идентифицировать рекурсивный вызов x = function(N/3), сложность которого составляет T(n/3). Далее следуют N дополнения, поэтому N операций для учета.

Поэтому рекуррентное соотношение для сложности этой функции составляет

T(n) = T(n/3) + n

Следовательно

T(n) = O(n.log3(n))