Theta выполнения рекурсии

Question

Как рассчитать время выполнения Тета этого данного кода:

void f(int n) 
{ 
    for (int i=3; i<n; ++i) 
     for (int j=0; j<i; ++j) 
      f(n-1); 
} 

До сих пор я получил это, но я не знаю, правильно ли это или как привести его в Тета нотации.

f(n) = n^2 * f(n-1) 
f(n) = n^2 * (n-1)^2 * f(n-2) 
f(n) = n^2 * (n-1)^2 * (n-2)^2 * f(n-3) 
... 

Answer 1

Поскольку каждый вложенный для цикла является O (N^2) сложность, и каждый раз при вызове функции внутри другой функции, сложность умножается, то вы в конечном итоге с O ((N!)^2), где N - это также количество повторений. Это, конечно, потому, что N! = N*(N-1)*(N-2)*...*(N-N+1), и все значения, используемые для создания факториала, являются квадратами.

Answer 2

Если заменить, что 3 с нуля (что, очевидно, ничего о & thetas не меняется), мы очень легко можем получить точное количество вызовов функции:

Θ _е() = 1
Θ _{е (п) =}п ⋅ Θ _{е (п -1)}∀ п> 0

Таким образом, используя commutativeness продукта,

_{н п} п
Θ _{е (п)} = П J = П J ⋅ П J = п! ⋅ n!
я = 1 я = 1 я = 1
= (п!)

Как сказал Джейсон.