5. analiza eficientei algoritmilor
vom dezvolta in acest capitol aparatul matematic necesar pentru analiza eficientei algoritmilor, incercand ca aceasta incursiune matematica sa nu fie excesiv de formala. apoi, vom arata, pe baza unor exemple, cum poate fi analizat un algoritm. o atentie speciala o vom acorda tehnicilor de analiza a algoritmilor recursivi.
5.1 notatia asimptotica
in capitolul 1 am dat un inteles intuitiv situatiei cand un algoritm necesita un timp in ordinul unei anumite functii. revenim acum cu o definitie riguroasa.
5.1.1 o notatie pentru ordinul lui
fie n multimea numerelor naturale pozitive sau zero si r multimea numerelor reale. notam prin n si r multimea numerelor naturale, respectiv reale, strict pozitive, si prin r multimea numerelor reale nenegative. multimea true, false de constante booleene o notam cu b. fie f n r o functie arbitrara. definim multimea
o f t n r c r n0 n n n0 tn cf n
cu alte cuvinte, o f se citeste or...