Toplista
- betöltés...
Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Magyarázatot kérnék egy algoritmus gépidejére!?
gyula205
kérdése
146
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!