Algoritmica 07/08
2. CRESCITA DELLE FUNZIONI
In informatica si usa la seguente notazione asintotica per indicare il possibile ordine di grandezza di una funzione. La variabile indipendente n è in genere un intero positivo e indica la “dimensione” dei dati di un problema (per es. il numero di bit necessario a descrivere i dati). La funzione di cui si studia l’ordine di grandezza è in genere proporzionale al tempo di calcolo (complessità in tempo), oppure alla memoria impiegata oltre a quella necessaria ai dati d’ingresso (complessità in spazio).
Notazione Θ
Θ(g(n)) = {f(n): esistono tre costanti positive c1, c2, n0, tali che 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n) per ogni n ≥ n0}
Cioè le funzioni f(n) e g(n) hanno lo stesso andamento al
crescere di n a meno di costanti moltiplicative, e contano solo i termini di ordine massimo. Per esempio f(n) = n2-3n+1 è di ordine Θ(n2).
La notazione Θ si impiega per esempio per indicare il tempo di un algoritmo di cui si conosce compiutamente il comportamento e che, a pari valore di n, si comporta allo stesso modo per tutti gli insiemi di dati di dimensione n che gli si presentano.
Notazione O
O(g(n)) = {f(n): esistono due costanti positive c, n0, tali che 0 ≤ f(n) ≤ cg(n) per ogni n ≥ n0}
Cioè la funzione f(n) ha un andamento che non sale al di sopra di g(n) al crescere di n, a meno di una costante moltiplicativa.
Anche qui contano solo i termini di ordine massimo. Per esempio f(n) = n2-3n+1 è di ordine O(n2), ma anche O(n3) ecc..
La notazione O si impiega per esempio per indicare il tempo di un algoritmo di cui non si conosce compiutamente il comportamento, ma che si sa che non può superare g(n); oppure che non si comporta allo stesso modo per tutti gli insiemi di dati di dimensione n che gli si presentano, ma per alcuni richiede tempo Θ(g(n)), per altri meno.
1
Notazione Ω
Ω(g(n)) = {f(n): esistono due costanti positive c, n0, tali che 0 ≤ cg(n) ≤ f(n) per ogni n ≥ n0}
Cioè la funzione f(n) ha un andamento che non scende al di sotto di g(n) al crescere di n, a meno di una costante moltiplicativa.
Anche qui contano solo i termini di ordine massimo. Per esempio f(n) = n2-3n+1 è di ordine Ω(n2), ma anche Ω(n log n) ecc..
La notazione Ω si impiega per esempio per indicare il limite inferiore al tempo di soluzione di un problema, che si applica quindi a tutti i suoi algoritmi di soluzione.
Altre notazioni
Ne ricordiamo solo una, che indica un limite non stretto. Abbiamo detto per esempio che f(n) = n2-3n+1 è di ordine O(n2), ma anche di ordine O(n3). Il primo ordine è stretto, il secondo non lo è.
Naturalmente se la f(n) è nota non ha senso usare O(n3), ma può essere utile indicare che f(n) è di ordine inferiore a questo.
Usiamo a questo proposito l’’ordine o:
Notazione o
o(g(n)) = {f(n): per qualsiasi costante positiva c, esiste una costante n0>0 tale che 0 ≤ f(n) < cg(n) per ogni n ≥ n0} Le definizioni di O e o sono simili, ma la seconda vale per
qualsiasi costante c. Per esempio f(n) = n2-3n+1 è di ordine o(n3).
Vedere esempi nel testo B.
2
