Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI MATEMATIKA U INFORMATICI

Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Brojni sistemi, Bulova algebra, binarna aritmetika itd.

Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Miladin Jovic » Utorak, 11. Oktobar 2016, 23:36

Imam jedan zadatak. Rekao bih da je više matematički, nego informatički.
Algoritam glasi
Kôd: Obeleži sve
def fibonacci(n):
 if n == 0 or n == 1:
 return 1
 else:
 return fibonacci(n - 1) + fibonacci(n - 2)

Traži se [inlmath]n[/inlmath]-ti član Fibonačijevog niza.
Naredba return izlazi iz funkcije i prebacuje tok izvršavanja na funkciju u okviru koje je pozvana istovremeno vraćajući određenu vrednost.
Algoritam je rekurzivan i nadam se da je jasan.
Merimo efikasnost na sledeči način. Ukoliko nije ispunjen uslov, izvršavaju se [inlmath]4[/inlmath] komande (provera u uslovu, dva rekurzivna poziva i operacija sabiranja). A ukoliko je uslov ispunjen (to će se desiti kada dođemo do funkcija sa argumentom 0 ili 1), imamo [inlmath]2[/inlmath] komande (proveru uslova i naredbu return).
Ja sam ovako započeo:
Neka je [inlmath]n[/inlmath] neki veliki broj tj. tražimo član u nizu sa veoma velikim indeksom.
Imamo:
[inlmath]f(n)=4+f(n-1)+f(n-2)[/inlmath]
Kada pozovemo prvi put ovu funkciju za to veliko [inlmath]n[/inlmath], izvršiće se one [inlmath]4[/inlmath] instrukcije. Dalje razlažemo [inlmath]f(n)=4+\bigg(4+f(n-2)+f(n-3)\bigg)+f(n-2)[/inlmath]
U primerima koje smo radili, dovoljno je razložiti još malo i uočiti neku pravilnost. Ovde nikako ne mogu da dokučim posle koliko koraka dolazimo do funkcija sa argumentima 0 ili 1, Takođe, ne znam kako da odredim koliko imamo ovih rekurzivnih funkcija u kojima će se izvršiti ove [inlmath]4[/inlmath] operacije (broj tih funkcija bi trebao da se izrazi preko [inlmath]n[/inlmath]).
Jasnije će biti sa slike o čemu se radi, iako nije baš neko umetničko delo :D . Ukoliko uzmemo da je [inlmath]n=5[/inlmath] imaćemo [inlmath]7[/inlmath] funkcija koje će izvršiti po [inlmath]4[/inlmath] operacije (obeležene crvenom bojom), i one koje će izvršiti dve operacije (obeležene crnom). Ovde možete videti principe rešavanja na jednostavnijim primerima, ukoliko nisam nešto objasnio kako treba.

Objašnjenje je malo opširnije, jer se verovatno niste susretali sa ovakvim tipom zadatka.
Prikačeni fajlovi
f(5).png
f(5).png (2.79 KiB) Pogledano 419 puta
Zaslužni forumaš
 
Postovi: 371
Zahvalio se: 243 puta
Pohvaljen: 125 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Daniel » Sreda, 12. Oktobar 2016, 09:01

Ako sam dobro razumeo šta je problem, ti zapravo ovde treba da izraziš [inlmath]f(n)[/inlmath] u funkciji od [inlmath]n[/inlmath], a to postižeš tako što ćeš rešiti nehomogenu linearnu diferencnu jednačinu drugog reda,
[dispmath]f(n)-f(n-1)-f(n-2)=4[/dispmath]
Da li znaš postupak njenog rešavanja? (Ukratko, nađeš rešenja odgovarajuće homogene jednačine pomoću karakteristične jednačine, zatim nađeš partikularno rešenje i na kraju ta dva rešenja sabereš.)
Ako treba da pokažem detaljniji postupak, reci.
Uglavnom, ako sam dobro razumeo da su početni uslovi [inlmath]f(0)=f(1)=2[/inlmath], onda treba da se dobije
[dispmath]f(n)=3\cdot\frac{5-\sqrt5}{5}\left(\frac{1-\sqrt5}{2}\right)^n+3\cdot\frac{5+\sqrt5}{5}\left(\frac{1+\sqrt5}{2}\right)^n-4[/dispmath]
što bi, uvrštavanjem različitih vrednosti za [inlmath]n[/inlmath], dalo
[dispmath]\begin{array}{|c|c|c|c|c|c|c|c|c|} \hline
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline
f(n) & 2 & 2 & 8 & 14 & 26 & 44 & 74 & 122\\ \hline
\end{array}[/dispmath]
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7739
Lokacija: Beograd
Zahvalio se: 4064 puta
Pohvaljen: 4124 puta

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Trougao » Sreda, 12. Oktobar 2016, 09:10

Ovo se lako resava kad se postavi rekurentna jednacina. Odredjivanje vremenske slozenosti rekurzivnih funkcija se najlakse odredjuje resavanjem odredjene rekurentne jednacine. Kako je ovo fibonacijev niz resenje njegove rekurentne jednacine je
[dispmath]a_n=\frac{1}{\sqrt5}\Big(\frac{1+\sqrt5}{2}\Big)^n-\frac{1}{\sqrt5}\Big(\frac{1-\sqrt5}{2}\Big)^n[/dispmath]
Imamo da [inlmath]\frac{1}{\sqrt5}\Big(\frac{1-\sqrt5}{2}\Big)^n\in O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)[/inlmath] pa:
[dispmath]\frac{1}{\sqrt5}\Big(\frac{1+\sqrt5}{2}\Big)^n-O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)=O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)+O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)=O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)[/dispmath]
Tako da je gornja procena vremenske slozenosti ove funkcije [inlmath]O\Big(\Big(\frac{1+\sqrt5}{2}\Big)^n\Big)[/inlmath]. A prostorna (memorijska) je [inlmath]O(n)[/inlmath] jer uvek ima najvise [inlmath]n[/inlmath] stekova za funkciju u svakom trenutku.
Trougao  OFFLINE
 
Postovi: 150
Zahvalio se: 57 puta
Pohvaljen: 105 puta

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Trougao » Sreda, 12. Oktobar 2016, 09:28

I da se dopunim zbog nepreciznosti, nema [inlmath]n[/inlmath] stekova vec [inlmath]n[/inlmath] memorijskih lokacija na steku dodeljenih funkciji.
Trougao  OFFLINE
 
Postovi: 150
Zahvalio se: 57 puta
Pohvaljen: 105 puta

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Daniel » Sreda, 12. Oktobar 2016, 11:49

Da se dopunim i ja. :) Izraz za [inlmath]f(n)[/inlmath],
Daniel je napisao:[dispmath]f(n)=3\cdot\frac{5-\sqrt5}{5}\left(\frac{1-\sqrt5}{2}\right)^n+3\cdot\frac{5+\sqrt5}{5}\left(\frac{1+\sqrt5}{2}\right)^n-4[/dispmath]

može se, nakon razvoja stepena binoma i nešto sređivanja, napisati i u sledećem obliku:

  • za [inlmath]n[/inlmath] parno:
    [dispmath]f(n)=\frac{3}{2^{n-1}}\Biggl({n\choose0}+{n\choose1}+{n\choose2}5+{n\choose3}5+{n\choose4}5^2+{n\choose5}5^2+\cdots+{n\choose n-1}5^{n/2-1}+{n\choose n}5^{n/2}\Biggr)-4[/dispmath]
  • za [inlmath]n[/inlmath] neparno:
    [dispmath]f(n)=\frac{3}{2^{n-1}}\Biggl({n\choose0}+{n\choose1}+{n\choose2}5+{n\choose3}5+{n\choose4}5^2+{n\choose5}5^2+\cdots+{n\choose n-1}5^{(n-1)/2}+{n\choose n}5^{(n-1)/2}\Biggr)-4[/dispmath]

a moglo bi se možda i dalje malo srediti, korišćenjem Paskalove formule [inlmath]{n\choose k-1}+{n\choose k}={n+1\choose k}[/inlmath]...
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7739
Lokacija: Beograd
Zahvalio se: 4064 puta
Pohvaljen: 4124 puta

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Miladin Jovic » Sreda, 12. Oktobar 2016, 14:17

Daniel je napisao:Da li znaš postupak njenog rešavanja? (Ukratko, nađeš rešenja odgovarajuće homogene jednačine pomoću karakteristične jednačine, zatim nađeš partikularno rešenje i na kraju ta dva rešenja sabereš.)

Ne znam, prvi put čujem za ovu vrstu jednačina.

@Trougao, A kako si došao do ovoga?
Trougao je napisao:Ovo se lako resava kad se postavi rekurentna jednacina. Odredjivanje vremenske slozenosti rekurzivnih funkcija se najlakse odredjuje resavanjem odredjene rekurentne jednacine. Kako je ovo fibonacijev niz resenje njegove rekurentne jednacine je
[dispmath]a_n=\frac{1}{\sqrt5}\Big(\frac{1+\sqrt5}{2}\Big)^n-\frac{1}{\sqrt5}\Big(\frac{1-\sqrt5}{2}\Big)^n[/dispmath]
Zaslužni forumaš
 
Postovi: 371
Zahvalio se: 243 puta
Pohvaljen: 125 puta

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Daniel » Sreda, 12. Oktobar 2016, 18:03

Miladin Jovic je napisao:Ne znam, prvi put čujem za ovu vrstu jednačina.

One su vrlo korisne (da ne kažem neophodne) kad hoćeš da na osnovu rekurentne formule dobiješ eksplicitni izraz za [inlmath]n[/inlmath]-ti član niza.
[inlmath]f(n)-f(n-1)-f(n-2)=4[/inlmath] je diferencna (rekurentna) nehomogena linearna jednačina drugog reda. Nehomogena jer na desnoj strani nemamo nulu (da imamo nulu bila bi homogena), linearna jer su koeficijenti uz [inlmath]f(n-k)[/inlmath] konstante, a drugog reda jer je [inlmath]f(n)[/inlmath] izraženo preko [inlmath]f(n-1)[/inlmath] i [inlmath]f(n-2)[/inlmath].
Neki opšti slučaj diferencne jednačine drugog reda bio bi [inlmath]c_0f(n)+c_1f(n-1)+c_2f(n-2)=\varphi(n)[/inlmath]. U našem slučaju je [inlmath]c_0=1,\;c_1=-1,\;c_2=-1,\;\varphi(n)=4[/inlmath].
Postupak dosta podseća na rešavanje nehomogenih diferencijalnih jednačina. Prvo nađemo rešenja odgovarajuće homogene diferencne jednačine, a nju dobijemo tako što na desnoj strani [inlmath]\varphi(n)[/inlmath] zamenimo nulom:
[dispmath]f(n)-f(n-1)-f(n-2)=0[/dispmath]
Za homogenu jednačinu [inlmath]c_0f(n)+c_1f(n-1)+c_2f(n-2)=0[/inlmath] karakteristična jednačina glasi [inlmath]c_0\lambda^2+c_1\lambda+c_2=0[/inlmath] (o čemu je i Trougao pisao u ovom postu, koji takođe preporučujem da pogledaš). Dakle, u ovom slučaju,
[dispmath]\lambda^2-\lambda-1=0[/dispmath]
Rešenja ove jednačine su
[dispmath]\lambda_{1,2}=\frac{1\pm\sqrt5}{2}[/dispmath]
Kada su rešenja karakteristične jednačine međusobno različita (kao što je ovde slučaj), tada opšte rešenje homogene jednačine ima oblik [inlmath]f_H(n)=A_1\lambda_1^n+A_2\lambda_2^n[/inlmath], gde su [inlmath]A_1[/inlmath] i [inlmath]A_2[/inlmath] konstante. Dakle,
[dispmath]f_H(n)=A_1\left(\frac{1-\sqrt5}{2}\right)^n+A_2\left(\frac{1+\sqrt5}{2}\right)^n[/dispmath]
Sada partikularno rešenje. Za slučaj [inlmath]\varphi(n)=\text{const}[/inlmath], partikularno rešenje je oblika [inlmath]f_P(n)=c_0[/inlmath]. Konstantu [inlmath]c_0[/inlmath] određujemo uvrštavanjem partikularnog rešenja u nehomogenu jednačinu:
[dispmath]\cancel{c_0}-\cancel{c_0}-c_0=4\quad\Longrightarrow\quad c_0=-4[/dispmath][dispmath]f_P(n)=-4[/dispmath]
Opšte rešenje polazne nehomogene jednačine će sada biti zbir opšteg rešenja homogene jednačine i partikularnog rešenja:
[dispmath]f(n)=f_H(n)+f_P(n)[/dispmath][dispmath]f(n)=A_1\left(\frac{1-\sqrt5}{2}\right)^n+A_2\left(\frac{1+\sqrt5}{2}\right)^n-4[/dispmath]
Koeficijente [inlmath]A_1[/inlmath] i [inlmath]A_2[/inlmath] određujemo iz zadatih početnih uslova. Naši početni uslovi su [inlmath]f(0)=2[/inlmath] i [inlmath]f(1)=2[/inlmath]:
[dispmath]f(0)=A_1+A_2-4=2[/dispmath][dispmath]f(1)=A_1\frac{1-\sqrt5}{2}+A_2\frac{1+\sqrt5}{2}-4=2[/dispmath]
čime dobijemo sistem od dve jednačine s dve nepoznate, [inlmath]A_1[/inlmath] i [inlmath]A_2[/inlmath]:
[dispmath]A_1+A_2=6[/dispmath][dispmath]A_1\frac{1-\sqrt5}{2}+A_2\frac{1+\sqrt5}{2}=6[/dispmath]
Rešavanjem ovog sistema dobije se
[dispmath]A_1=3\cdot\frac{5-\sqrt5}{5},\qquad A_2=3\cdot\frac{5+\sqrt5}{5}[/dispmath]
pa je konačno rešenje polazne nehomogene diferencne jednačine
[dispmath]\enclose{box}{f(n)=3\cdot\frac{5-\sqrt5}{5}\left(\frac{1-\sqrt5}{2}\right)^n+3\cdot\frac{5+\sqrt5}{5}\left(\frac{1+\sqrt5}{2}\right)^n-4}[/dispmath]


Možeš pokušati, radi vežbe, da na sličan način izvedeš formulu i za [inlmath]n[/inlmath]-ti član Fibonačijevog niza. Kreneš od rekurentne formule [inlmath]f(n)=f(n-1)+f(n-2)[/inlmath], uz početne uslove [inlmath]f(0)=0,\;f(1)=1[/inlmath] (ovde sad nemaš nehomogenu, već homogenu jednačinu). Za [inlmath]n[/inlmath]-ti član niza dobićeš upravo onaj izraz koji je Trougao naveo, za koji si pitao kako je došao do njega...
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 7739
Lokacija: Beograd
Zahvalio se: 4064 puta
Pohvaljen: 4124 puta

Re: Računanje efikasnosti algoritma sa aspekta vremenske kompleksnosti

Postod Trougao » Sreda, 12. Oktobar 2016, 19:22

Daniel je odlicno napisao kako se dolazi do onog izraza. Svaku rekurzivno zadatu funkciju mozes predstaviti kao rekurentnu jednacinu. Pocetni uslovi [inlmath]a_0,a_1[/inlmath] su ti oni if-ovi tj sta vracaju. Ako te vise interesuju i rekurentne jednacine i slozenost algoritama savetovao bih te da skines sa interneta knjigu Programiranje 2 od Predraga Janicica i Filipa Marica(nju smo koristili za programiranje 2 na fakultetu). Profesor Janicic ju je objavio na svom sajtu. Knjiga nije jos do kraja zavrsena ali ima deo sa kompleksnoscu algoritama i raznim tipovima rekurentnih jednacina i njihovim resenjima. Ima i sajt od prosle godine za programiranje 2 koji su nastavnici MATF-a napravili za studente brisu sadrzaj tek u decembru ili januaru pa postavljaju novi kad pocne prolecni semestar i krene nova grupa www.programiranje2.matf.bg.ac.rs.
Trougao  OFFLINE
 
Postovi: 150
Zahvalio se: 57 puta
Pohvaljen: 105 puta


Povratak na MATEMATIKA U INFORMATICI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 4 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Četvrtak, 24. Oktobar 2019, 01:51 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs