Определение времени выполнения следующего кода (рекурсия с циклом внутри)

Question

У меня есть следующий код, и мне нужно определить время работы этого алгоритма.

int res=0; 
if (n <= 1) 
    return 1;
for (int i = 0; i < n; i++) 
    res += Catalan(i) * (Catalan(n - i - 1); 
return res;

Мне трудно определить время выполнения из-за цикла внутри рекурсии. Я знаю, что мне нужно преобразовать ее в формулу регрессии, а затем проанализировать ее, но я не уверен, как это сделать.

Answer 1

Давайте упростим вашу функцию до:

    for (int i=0; i< n; i++) 
        res += Catalan(i)*(Catalan(i-1); 
    return res;

это упрощение не должно влиять на сложность времени.

Пусть n = 1:

   1 
   /\
  0  0

, тогда у нас будет 3 вызова каталонской функции.

Если n = 2, то для каталонского (i) мы будем иметь:

     2
     /
    1 
   /\ 
  0 0 

и для каталонского (i-1)

   1 
   /\
  0  0

, поэтому в общей сложности у нас будет:

     2      
     /\    
    1  1   
   /\  /\  
  0 0 0  0 

, если i = 3, то:

          3
       /     \
      2       2 
     /\       /\
    1  1     1  1
   /\  /\    /\ /\
  0 0 0  0  0 0 0 0

Мне кажется, O(2^n) сложность

Answer 2

Чтобы получить первую идею, профилируйте ее с различными размерами ввода.

Если вы построите график времени выполнения по размеру входных данных, вы довольно легко получите представление, если это O (N) или что-то вроде O (N²).

Тогда у вас есть представление о сложности, которую вы ищете, внимательно посмотрите на свой код, чтобы найти подтверждение формата ваших наблюдений.