Продолжительность этого алгоритма

Question

У меня есть этот алгоритм, и я не могу понять, какова его временная сложность.

int oc(int n) { 
    if (n == 0) 
    { 
     return 0; 
    } 
    int s = p[n][0]; 
    for (int i = n-1; i > 0; i--) 
    { 
     int a = p[n][i] + oc(i); 
     if (s > a) 
     { 
      s = a; 

     } 
    } 
    return s; 
} 

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

Answer 1

Пусть T(n) является сложность вычисления oc(n). Поскольку для вычисления oc(n) вы работаете цикл от n-1 к 1 и рекурсивно вызывая oc(i), следовательно

T(n)=T(n-1)+T(n-2)+...+T(1) (*).

Если вместо Т (п-1) положим

T(n-1)=T(n-2)+T(n-3)+...+T(1)

в (*) мы получим:

T(n)=2*(T(n-2)+...+T(1))

Если мы будем продолжать ту же итерацию для T(n-2), T(n-3) и т.д. мы будем заключать tô следующее равенство:

T(n)=2*(T(n-2)+...+T(1)) 
=4*(T(n-3)+...+T(1)) 
=2^i*(T(n-i-1)+...+T(1)) 
=2^n*T(1)/2=O(2^n). 

Причина этой сложности - ваш алгоритм вычисления же много раз. Если вы запоминаете значения в массиве, для которых вы рассчитали значение функции oc, и добавьте проверку в первую часть функции, которая вернет значение непосредственно из массива (в случае, если оно уже рассчитано), вместо того, чтобы запускать цикл и снова делать то же самое задание, сложность алгоритма будет резко изменяться и будет O(n), так как алгоритм будет вычислять все значения и сохранять при первой итерации ваших циклов.

Answer 2

Это O (2 ⁿ). Посмотрите, как количество итераций выстраивается для увеличения п:

n | f(n) = total iterations 
---+------------------------------------------------- 
1 | 0 
2 | 1 + f(1) = 1 + 0 = 1 
3 | 2 + f(2) + f(1) = 1 + 2f(2) = 1 + 2.1 = 3 
4 | 3 + f(3) + f(2) + f(1) = 1 + 2f(3) = 1 + 2.3 = 7 
...| ... 
n | .... 1 + 2.f(n-1) = 2^(n-1) - 1