** $k=2*p-1$ si $k+1=2*p$: Pentru $k$, va trebui sa rezolvam la nivelul urmator de recursivitate problema pentru valorile $p-1$ si $p$, iar pentru $k+1$ va trebui sa rezolvam problema pentru valoarea $p$ ; asadar, la urmatorul nivel de recursivitate va trebui sa rezolvam problema doar pentru valorile distincte $p-1$ si $p$.
In concluzie, la fiecare nivel al recursivitatii, avem de rezolvat, de fapt, doar $2$ probleme distincte. Prin urmare, daca memoizam rezultatele pentru fiecare valoare pentru care generam cate o permutare in cadrul algoritmului descris anterior, vom ajunge la o complexitate $O(N)$, in loc de $O(N*logN)$. Aceasta complexitate se obtine din urmatoarea relatie: $N + 2 * (N/2 + N/4 + N/8 + ...) = 3*N$.

Articol scris de 'Meditatii Informatica':https://meditatii-informatica.com

h2(#kboard). 'Kboard':problema/kboard