Nenad Božidarević
Jul 2011.

Rešavanje rekurentnih jednačina

Nakon nešto duže pauze uglavnom prouzrokovane ispitnim rokom, vraćamo se programiranju i matematici…

Rekurentne formule predstavljaju poseban oblik zapisivanja vrednosti nekog niza. Jedna od najpoznatijih ovakvih relacija je svakako Fibonačijev niz, u kome vrednost nekog člana niza zavisi od vrednosti prethodna dva.

F_n = F_{n-1} + F_{n-2}, ~ F_0 = 0, ~ F_1 = 1

Ukoliko u programu želimo da izračunamo neki član ovog (ili bilo kog drugog) niza, potrebno je da krenemo od vrednosti koje su nam date i iterativno dođemo do željenog člana, pritom prolazeći kroz sve njegove prethodnike. Naravno, moguće je i rešavanje relacije tako da formula zavisi samo od datih vrednosti i N, ali to bi bilo previše komplikovano za implementaciju.

Iako je ovaj pristup krajnje jednostavan, u nekim slučajevima nije moguće primeniti ga usled problema sa efikasnošću. Linearne homogene rekurentne formule, koje ću obraditi u ovom tekstu, mogu biti vremenski zahtevne ukoliko se traži član se velikim indeksom. Ukoliko svaki član zavisi od 10 prethodnih, a njegov indeks je 100.000.000, ukupno će biti potrebno milijardu sabiranja, što je apsolutno nepotrebno. Postoji i komplikovaniji, ali daleko brži pristup.

Pročitaj ostatak teksta