Rekurzivne / rekurenčne enačbe

matix · 10. nov 2009

Živjo,

pri analizi časovne zahtevnosti rekurzivnih algoritmov mi probleme delajo rekurenčne enačbe.

Recimo da imam formulo F(n)=2 F(n-1) + F(n-2); robni pogoji: F(0)=0, F(1)=1, F(2)=2

Jaz sem se lotil takole:

c * x^n = c * 2 * x^n-1 + c x^n-2, pokrajšamo in:
x^2 = 2x +1
(x+1)^2 = 0
x1,2=-1

Potem pa se mi zatakne, kaj moram narediti naprej, upoštevajoč tiste robne pogoje zgoraj? Vem, kako se naredi, če dobiš 2 različni rešitvi za x, vendar kolikor vem, je stvar malo drugačna, če dobiš obe ničli enaki.

Tnx.

mosseero · 10. nov 2009

Res narediš tako, kot si rekel. Člen stopnje n zamenjaš z λ^n, člen stopnje n-1 z λ^(n-1) itd. Na ta način dobiš karakteristični polinom. To si vse pravilno naredil, edino razstavil si ga narobe. V tvojem primeru pride rešitev λ1,2=1, ne -1.

Splošna rešitev je po teoriji enaka F(n)=a * 1^n+b * n^1 * 1^n, na kratko je torej F(n)=a+b*n. Sedaj moraš iz ZAČETNIH pogojev določiti a in b. To je lahko, ker po vstavitvi n=0 dobiš F(0)=0=a, po drugi vstavitvi pa F(1)=b=1. Končna rešitev je torej F(n)=0+1*n oz. F(n)=n.

To je to.

matix · 10. nov 2009

Si prepričan, da je tako? Kolikor vem, ima rekurzija eksponentno rast!

To dokaže tudi izračun, če damo argumente v enačbo:
n f(n)
5 29
6 70
7 169
8 408

V bistvu to računam (časovno zahtevnost) za sledeči rekurzivni programček, da se bomo zastopili:

Koda:

public static int re(int n){
		if(n==0) return 0;
		else if(n==1) return 1;
		else if(n==2) return 2;
		return 2*re(n-1)+re(n-2); 	
	}

mosseero · 10. nov 2009

Edit: če ne bi bila oba blond, bi opazila, da imava napačno karakteristično enačbo in posledično napačno rešitev.

Prava karakteristična enačba je oblike λ^2 - 2λ - 1=0.

No, rešitvi te enačbe sta λ1=1+Sqrt[2] in λ2=1-Sqrt[2]. Splošna rešitev rekurzivne enačbe je F(n)=a λ1^n + b λ2^n. Sedaj vstaviš oba začetna pogoja, t.j., F(0)=0 in F(1)=1, da dobiš sistem dveh linearnih enačb z dvema neznankama, ki je enolično rešljiv. Končna rešitev je F(n)=Sqrt[2]/4 (1+Sqrt[2])^n - Sqrt[2]/4 (1-Sqrt[2])^n. Preverjeno na vseh tvojih primerih.

philips · 10. nov 2009

Časovne zahtevnosti za rekurzivne algoritme nismo računali, smo pa pri diskretnih strukturah pretvarjali rekurzivno enačbo v nerekurzivno (seveda vedno ne gre).

Tvoja enačba je identična fibonacciju, samo začetni pogoji so malenkost drugačni. Nerekurzivna oblika fibonaccija je:

$968be88f42e32712cb10d89a765ce708.png$

Torej vidiš da je zadeva res eksponentna.

To moraš obvezno analitično narediti? Mi smo namreč to vse numerično delali - si izmeril časovno zahtevnost za N=100 in recimo N=200 in potem izračunal vse koeficiente (po potrebi si naredil še več meritev).

Ker analitičen izračun časovne zahtevnosti ne upošteva dejanskega izvajanja na računalniku - recimo pred vsakim klicem funkcije se vsi registri push-ajo, po return stavku pa se nazaj pop-ajo. To seveda zavzame kar nekaj časa, ki pa ga matematiki ne vidijo

mosseero · 10. nov 2009

Zakaj bi kompliciral z aproksimacijami, če imaš lahko točno analitično rešitev?

matix · 10. nov 2009

Citat:
Uporabnik philips pravi:
To moraš obvezno analitično narediti? Mi smo namreč to vse numerično delali - si izmeril časovno zahtevnost za N=100 in recimo N=200 in potem izračunal vse koeficiente (po potrebi si naredil še več meritev).

Naredit moramo analitično, nato pa primerjat analitični graf in graf dejanskega izmerjenega časa.

Žal iz mojega algoritma ne znam narediti drugačne rekurzivne formule, kot sem jo sprva zapisal

mosseero · 10. nov 2009

Poglej moj editiran post. Dejansko imaš pravilno enačbo, samo oba sva jo narobe reševala. Tudi splošna rešitev, ki sem jo napisal, funkcionira, kar sem preveril na vseh tvojih n-jih do vključno n=8.

mosseero · 10. nov 2009

Citat:
Uporabnik matix pravi:
Živjo,

pri analizi časovne zahtevnosti rekurzivnih algoritmov mi probleme delajo rekurenčne enačbe.

Recimo da imam formulo F(n)=2 F(n-1) + F(n-2); robni pogoji: F(0)=0, F(1)=1, F(2)=2

Jaz sem se lotil takole:

c * x^n = c * 2 * x^n-1 + c x^n-2, pokrajšamo in:
x^2 = 2x +1 Do tule je vse prav.
(x+1)^2 = 0 Tole je pa narobe. Ko daš 2x+1 na levo, dobiš enačbo x^2-2x-1=0.
x1,2=-1

Potem pa se mi zatakne, kaj moram narediti naprej, upoštevajoč tiste robne pogoje zgoraj? Vem, kako se naredi, če dobiš 2 različni rešitvi za x, vendar kolikor vem, je stvar malo drugačna, če dobiš obe ničli enaki.

Tnx.

matix · 10. nov 2009

Super! Tebi moram pa počasi res poslat en darilni paket

philips · 11. nov 2009

Citat:
Uporabnik mosseero pravi:
Zakaj bi kompliciral z aproksimacijami, če imaš lahko točno analitično rešitev?

Ampak analitična rešitev ne bo odraz dejanske časovne zahtevnosti algoritma, ko ga poženeš v določenem programskem jeziku.

Lani sem imel primer enega algoritma s polinomsko časovno zahtevnostjo in ker sem znotraj glavne funkcij klical veliko drugih funkcij, sem dobil za časovno zahtevnost en polinom, ki je bil kar za dve stopnji višji kot bi moral biti. Nato sem moral tiste izračune prestavil v glavno funkcijo, da sem dosegel časovno zahtevnost na papirju (beri: analitično izračunana).

Tku · 12. nov 2009

Citat:
Uporabnik matix pravi:
Žal iz mojega algoritma ne znam narediti drugačne rekurzivne formule, kot sem jo sprva zapisal

Kot je meni znano, lahko vsak rekurziven algoritem predelaš v iterativnega, če ti to kaj pomaga.

Iskanje

Iskanje

Rekurzivne / rekurenčne enačbe

matix

Fizikalc

mosseero

fizik´alc

matix

Fizikalc

mosseero

fizik´alc

philips

Guru

mosseero

fizik´alc

matix

Fizikalc

mosseero

fizik´alc

mosseero

fizik´alc

matix

Fizikalc

philips

Guru

Tku

Pripravnik

Podobne teme