Nemam ideju kako mogu da resim ovaj zadatak https://petlja.org/biblioteka/r/FibonacijeviPodnizovi
Koliko shvatam tekst, na ulazu moze biti mnogo brojeva (N je veliko), ali nema velikih vrednosti – najveca moguca vrednost je samo M = 10000. Da bi izbegli cuvanje svih N brojeva i mogli brzo da proverimo da li je neki broj na raspolaganju, mozemo u niz sacuvati "da li ulaz sadrzi broj i" (posto se na izlazu traze i indeksi, dobro bi bilo sacuvati i prvi indeks gde se i pojavljuje).
Sada mozemo da probamo svaki moguci par prvih elemenata niza (njih M^2) i redom racunamo naredni element dok god ne naidjemo na neki koji se ne nalazi u ulazu (tj. nije markiran u nizu). Iako ovo naizgled deluje kao spor algoritam, sa tri ugnjezdene petlje i samim tim mozda \mathcal{O}(N^3), slozenost je u stvari primetno bolja jer vrednosti Fibonacijevog niza rastu brzo, tako da se treca petlja (koja racuna elemente niza) nece izvrsavati dugo.
Malo bolja analiza slozenosti (nebitna za resavanje zadatka): elementi fibonacijevog niza rastu eksponencijalno (za pocetne clanove 1, 1, n-ti clan je srazmeran sa \phi^n, gde je \phi zlatni presek). Samim tim, vrednost koju racunamo u unutrasnjoj petlji ce preci M u \mathcal{O}(\log M) koraka, tako da je ukupna slozenost \mathcal{O}(M^2 \log M).
2 Likes