|
|
In generale, nel valutare il tempo di calcolo T(n), è molto difficile quantificare con esattezza il numero di operazioni elementari eseguite. Questa difficoltà viene aggirata valutando il numero di operazioni in ordine di grandezza, ovvero come limitazione della funzione T(n), al tendere all’ infinito della dimensione n, trascurando le costanti. Si parla quindi di complessità computazionale asintotica in ordine di grandezza, o brevemente complessità di una procedura. Si usano le notazioni “O”, “OMEGA”, definite come segue:
Individua la limitazione superiore al comportamento asintotico di T(n).
Individua la limitazione inferiore al comportamento asintotico di T(n).
Ogni operazione elementare ha ordine di grandezza O(1), non danno invece contributo unitario le istruzioni condizionali, le iterazioni, le chiamate a procedure e funzioni.
Si consideri i seguenti codici in linguaggio C:
Ricapitolando per stabilire la complessità di un algoritmo, se ne studia l’ ordine di grandezza O(T(n)) del tempo di calcolo T(n), inteso come numero di operazioni elementari eseguite nel caso pessimo, in funzione della dimensione n dei dati in ingresso.
Per saperne di più consulta i seguenti approfondimenti:
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.