h2. Indicaţii de rezolvare

O implementare directă a relaţiei de recurenţă în complexitate liniară ar trebui să obţină $20$ de puncte şi se găseşte 'aici':/job_detail/382677?action=view-source.

O implementare directă a relaţiei de recurenţă în complexitate liniară ar trebui să obţină $20$ de puncte şi se găseşte 'aici':job_detail/382677?action=view-source.

Pentru a obţine $100$ de puncte trebuie găsită o metodă eficientă de a rezolva această recurenţă. Ne vom folosi de 'înmulţirea matricelor':http://en.wikipedia.org/wiki/Matrix_multiplication#Ordinary_matrix_product în felul următor: la pasul <tex> n </tex> vom avea deja calculate <tex> F_{n-2} </tex> şi <tex> F_{n-1} </tex> şi vom dori să îl aflăm pe <tex> F_{n} </tex>:

0 & 1 \\
1 & 1 \end{array} \right)\] </tex>.

Ştim că <tex>M_{i} = M_{i-1} \times Z </tex> şi mai ştim că <tex>M_{i-1} = M_{i-2} \times Z </tex>. Din proprietatea de asociativitate a înmulţirii matricelor rezultă că <tex>M_{i} = M_{i-2} \times Z^2 </tex>. Inductiv, rezultă egalitatea <tex>M_{i} = M_{1} \times Z^{i-1}</tex>. 'Soluţia':/job_detail/372680?action=view-source optimă se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, având complexitatea <tex>O(log K)</tex>. Constanta ce se ascunde în spatele acestei complexităţi este egală cu numărul de operaţii efectuate la fiecare pas al ridicării la putere, adică cu dimensiunea matricii constante <tex> Z </tex> la puterea a <tex>3</tex>-a, care este <tex>8</tex>.

Ştim că <tex>M_{i} = M_{i-1} \times Z </tex> şi mai ştim că <tex>M_{i-1} = M_{i-2} \times Z </tex>. Din proprietatea de asociativitate a înmulţirii matricelor rezultă că <tex>M_{i} = M_{i-2} \times Z^2 </tex>. Inductiv, rezultă egalitatea <tex>M_{i} = M_{1} \times Z^{i-1}</tex>. 'Soluţia':job_detail/382679?action=view-source optimă se foloseşte de 'ridicarea la putere în timp logaritmic':/problema/lgput, având complexitatea <tex>O(log K)</tex>. Constanta ce se ascunde în spatele acestei complexităţi este egală cu numărul de operaţii efectuate la fiecare pas al ridicării la putere, adică cu dimensiunea matricii constante <tex> Z </tex> la puterea a <tex>3</tex>-a, care este <tex>8</tex>.

h2. Aplicaţii