Вычисление сложности функции

Question

У меня есть функция для вычисления длины самой продолжительной последовательности. Здесь arr [] - массив длины n. И lisarr имеет длину n для хранения длины элемента i.

Мне трудно вычислить выражение повторения, которое является вводом для основной теоремы.

int findLIS(int n){ 
     if(n==0) 
      return 1 ; 
     int res; 
     for(int i=0;i<n;i++){ 
      res=findLIS(i); 
      if(arr[n]>arr[i] && res+1>lisarr[n]) 
       lisarr[n]=res+1; 
     } 
     return lisarr[n]; 
    } 

Просьба указать способ повторения. Должно ли это T(n)=O(n)+T(1)?

Answer 1

Это O(2^n). Вычислим точное число итераций и обозначим его f(n). Рекуррентное отношение: f(n) = 1 + f(n-1) + f(n-2) + .. + f(1) + f(0), с f(1)=2 и f(0)=1, что дает f(n)=2*f(n-1) и, наконец, f(n)=2^n.

Доказательство по индукции:

Base п = 0 -> только одна итерация функции. Предположим, что f(n)=2^n. Затем для ввода n+1 мы имеем f(n+1) = 1 + f(n) + f(n-1) + .. + f(1) + f(0) = 1 + (2^n + 2^(n-1) + .. + 2 + 1) = 1 + (2^(n+1) - 1)=2^(n+1).. Номер один в начале происходит от части за пределами цикла for, и сумма является следствием цикла for. У вас всегда есть один рекурсивный вызов для каждого i в {0,1,2,..,n}.