Calcule o número de iterações em loop aninhado incomum

Question

Estou tentando calcular o número de iterações de uma sequência de loops aninhados do formulário:

\ begin {equation} N=sum_ {j= 0} ^ {j_t} \ sum_ {k= 0} ^ {j}} s sum_ {l= 0} ^ {k} \ sum_ {n= n_0} ^ {n_t} 1 \ end {equation}

onde $ j_t \ ge 0 $ e $ n_t \ ge 0 $ são constantes conhecidas. < / p >.

para $ n_0= 0 $ O caso é trivial e pode ser calculado usando o procedimento padrão ( soma Número de tempos de instrução é executado no loop de triple aninhado )

O problema é que no meu caso $ n_0 $ é dado por uma expressão mais complexa:

$$ N_0=BEGIN} 0 & \ text {se} k-2l \ lt0, \\ n_t & \ text {se} k-2l \ gt n_t, \\ k-2l & \ text {de outra forma.} \ fim {casos} $$

Basicamente, o valor inicial da $ n $ na última soma é $ K-2L $ , exceto quando seu valor é menor / maior que os limites inferiores / maiores da soma, caso em que é substituído pelo valor extremo correspondente do intervalo ( $ 0 $ ou $ n_t $ ).

Alguma idéia?

Answer 1

Se você quiser calcular um limite superior da complexidade assintótica, você pode considerar o valor máximo para a soma mais interna.Assim, $ \ sum_ {n= n_0} ^ {n_t} 1 \ leqslant n_t + 1 $ .Portanto, teremos:

$$ N \ leqslant \ sum_ {j= 0} ^ {j_t} \ sum_ {k= 0} ^ j \ sum_ {l= 0} ^ k (n_t + 1)=sum_ {j= 0} ^ {j_t} \sum_ {k= 0} ^ j (n_t + 1) (k + 1)= (n_t + 1) \ sum_ {j= 0} ^ {j_} \ sum_ {k= 0} ^ j (k + 1)= $$ $$ (n_t + 1) \ sum_ {j= 0} ^ {j_t} \ frac {(j + 1) (j + 2)} {2}=theta (n_t (j_t) ^ 3) $$

Portanto, $ n= O (n_t (j_t) ^ 3) $ .