...nte, O f se citeste ordinul lui f este multimea tuturor functiilor t marginite superior de un multiplu real pozitiv al lui f, pentru valori suficient de mari ale argumentului. Vom conveni sa spunem ca t este in ordinul lui f sau, echivalent, t este in O f , sau t I O f chiar si atunci cand valoarea f n este negativa sau nedefinita pentru anumite valori n n0. In mod similar, vom vorbi despre ordinul lui f chiar si atunci cand valoarea tn este negativa sau nedefinita pentru un numar finit de valori ale lui n in acest caz, vom alege n0 suficient de mare, astfel incat, pentru n n0, acest lucru sa nu mai apara. De exemplu, vom vorbi despre ordinul lui nlog n, chiar daca pentru n 0 si n 1 functia nu este definita. In loc de t I O f , uneori este mai convenabil sa folosim notatia tn I O f n, subintelegand aici ca tn si f n sunt functii.Fie un algoritm dat si fie o functie t N R astfel incat o anumita implementare a algoritmului sa necesite cel mult tn unitati de timp pentru a rezolva un caz de marime n, n I N. Principiul invariantei mentionat in Capitolul 1 ne asigura ca orice implementare a algoritmului necesita un timp in ordinul lui t. Mai mult, acest algoritm necesita un timp in ordinul lui f pentru orice functie f N R pentru care t I O f . In particular, t I Ot. Vom cauta in general sa gasim cea mai simpla functie f, astfel incat t I O f .Proprietatile de baza ale lui O f sunt date ca exercitii Exercitiile 5.1-5.7 si este recomandabil sa le studiati inainte de a trece mai departe.Notatia asimptotica defineste o relatie de ordine partiala intre functii si deci, intre eficienta relativa a diferitilor algoritmi care rezolva o anumita problema. Vom da in continuare o interpretare algebrica a notatiei asimptotice. Pentru oricare doua functii f , g N R, definim urmatoarea relatie binara f g daca O f Og. Relatia este o relatie de ordine partiala in multimea functiilor definite pe N si cu valori in R Exercitiul 5.6. Definim si o relatie de echivalenta f g daca O f Og.In multimea O f putem inlocui pe f cu orice alta functie echivalenta cu f. De exemplu, lg n ln n log n si avem Olg n Oln n Olog n. Notand cu O1 ordinul functiilor marginite superior de o constanta, obtinem ierarhiaO1 Olog n On On log n On2 On3 O2nAceasta ierarhie corespunde unei clasificari a algoritmilor dupa un criteriu al performantei. Pentru o problema data, dorim mereu sa obtinem un algoritm corespunzator unui ordin cat mai la stanga. Astfel, este o mare realizare daca in locul unui algoritm exponential gasim un algoritm polinomial.In Exercitiul 5.7 este data o metoda de simplificare a calculelor, in care apare notatia asimptotica. De exemplu,n33n2n8 I On33n2n8 Omaxn3, 3n2n8 On3Ultima egalitate este adevarata, chiar daca maxn3, 3n2n8 n3 pentru 0 n 3, deoarece notatia asimptotica se aplica doar pentru n suficient de mare. De asemenea,n3-3n2-n-8 I On32n32-3n2-n-8 Omaxn32, n32-3n2-n-8 On32 On3chiar daca pentru 0 n 6 polinomul este negativ. Exercitiul 5.8 trateaza cazul unui polinom oarecare.Notatia O f este folosita pentru a limita superior timpul necesar unui algoritm, masurand eficienta algoritmului respectiv. Uneori este util sa estimam si o limita inferioara a acestui timp. In acest scop, definim multimea f It N R c I R n0 I N n n0 itn cf nsSExista o anumita dualitate intre notatiile O f si f . Si anume, pentru doua functii oarecare f, g N R, avem f I Og, daca si numai daca g I f .O situatie fericita este atunci cand timpul de executie al unui algoritm este limitat, atat inferior cat si superior, de cate un multiplu real pozitiv al aceleiasi functii. Introducem notatiaQ f O f f numita ordinul exact al lui f. Pentru a compara ordinele a doua functii, notatia Q nu este insa mai puternica decat notatia O, in sensul ca relatia O f Og este echivalenta cu Q f Qg.Se poate intampla ca timpul de executie al unui algoritm sa depinda simultan de mai multi parametri. Aceasta situatie ...
Download