Toplista
- betöltés...
Segítség!
Ahhoz, hogy mások kérdéseit és válaszait megtekinthesd, nem kell beregisztrálnod, azonban saját kérdés kiírásához ez szükséges!
Magyarázatot kérnék egy algoritmus gépidejére!?
gyula205
kérdése
109
Két számsorozat első huszonnégy elemét szeretném kiszámolni a egy matek szoftver segítségével a következő algoritmussal:
`c_0=1` és `s_0=1` kezdeti értékek mellett, a `c(n):=frac{-1}{3n}sum_(k=0)^(n-1)s_k*s_(n-1-k)` illetve
`s(n):=frac{1}{3n+1}sum_(k=0)^(n)c_k*c_(n-k)` rekurzióval.
A `(c_7=- 584929/53362030176, s_7= - 25469/4104771552)` számpáron kb. 3,5 s;
`(c_8=1273037/640344362112, s_8=225187/200107613160)` számpáron kb. kb. 21 s;
`(c_9=- 202602551/561902177753280 , s_9=- 1605555011/7866630488545920)`
számpáron kb. 123 s-t dolgozott egy asztali számítógép. Ha `n`-edik indexhez tartozó
gépidőt `t(n)`-el jelöljük, akkor `n>9` esetén igaz-e `frac{t(n+1)}{t(n)} ge 6` becslés?
A válaszokat megköszönöm.
`c_0=1` és `s_0=1` kezdeti értékek mellett, a `c(n):=frac{-1}{3n}sum_(k=0)^(n-1)s_k*s_(n-1-k)` illetve
`s(n):=frac{1}{3n+1}sum_(k=0)^(n)c_k*c_(n-k)` rekurzióval.
A `(c_7=- 584929/53362030176, s_7= - 25469/4104771552)` számpáron kb. 3,5 s;
`(c_8=1273037/640344362112, s_8=225187/200107613160)` számpáron kb. kb. 21 s;
`(c_9=- 202602551/561902177753280 , s_9=- 1605555011/7866630488545920)`
számpáron kb. 123 s-t dolgozott egy asztali számítógép. Ha `n`-edik indexhez tartozó
gépidőt `t(n)`-el jelöljük, akkor `n>9` esetén igaz-e `frac{t(n+1)}{t(n)} ge 6` becslés?
A válaszokat megköszönöm.
Jelenleg 1 felhasználó nézi ezt a kérdést.
rekurzió, Algoritmus, gépidő
rekurzió, Algoritmus, gépidő
0
Felsőoktatás / Informatika
Válaszok
1
gyula205
válasza
Végül is találtam egy áthidaló megoldást a gépidő csokkentésére.
A két rekurzió egymásba láncoltan eredményezi a gépidő drasztikus növekedését. Ha kitartunk mellettük, akkor valójában igaz a a felírt egyenlőtlenség (becslés). `c_24`-re illetve `s_24` szánt gépidő "brutális" lenne, ha nem találnánk valami más utat.
A kiszámított értékeket két tömbbe elhelyezve (legyen ez `C` illetev `S`), direkten lépésenként alkalmazzuk a rekurziót. Ekkor először a `c_n` értékét számítjuk, ami lényegében egy szorzatösszeg. Majd `C`-t kiegészítve betesszük ezt az utolsó helyre.
Megismételve ugyanezeket a lépéseket `s_n` értékre és az `S` tömbre majd az egész ciklust újra ismételjük.
A két rekurzió egymásba láncoltan eredményezi a gépidő drasztikus növekedését. Ha kitartunk mellettük, akkor valójában igaz a a felírt egyenlőtlenség (becslés). `c_24`-re illetve `s_24` szánt gépidő "brutális" lenne, ha nem találnánk valami más utat.
A kiszámított értékeket két tömbbe elhelyezve (legyen ez `C` illetev `S`), direkten lépésenként alkalmazzuk a rekurziót. Ekkor először a `c_n` értékét számítjuk, ami lényegében egy szorzatösszeg. Majd `C`-t kiegészítve betesszük ezt az utolsó helyre.
Megismételve ugyanezeket a lépéseket `s_n` értékre és az `S` tömbre majd az egész ciklust újra ismételjük.
0
- Még nem érkezett komment!