Ordine di complessità è un termine utilizzato in informatica per misurare l'efficienza di un algoritmo o di un programma. Si riferisce alla quantità di tempo e risorse necessarie per risolvere un problema o eseguire un'attività. Nella programmazione, l'ordine di complessità è solitamente espresso in termini di Grande O notazione, che fornisce un limite superiore ai requisiti di tempo o spazio di un algoritmo. In questo articolo discuteremo dell'ordine di complessità nel linguaggio di programmazione C e del suo significato.
Ordine di complessità nel linguaggio di programmazione C:
Nella programmazione C, l'ordine di complessità di un algoritmo dipende dal numero di operazioni eseguite dal programma. Ad esempio, se abbiamo un array di dimensione n e vogliamo cercare un particolare elemento nell'array, l'ordine di complessità dell'algoritmo dipenderà dal numero di elementi nell'array. Se eseguiamo a Ricerca lineare attraverso l'array, sarà l'ordine di complessità SU) , il che significa che il tempo impiegato per la ricerca dell'elemento aumenterà linearmente con la dimensione dell'array. Se usiamo a Algoritmo di ricerca binaria lo sarà invece l’Ordine della Complessità O(log n) , il che significa che il tempo impiegato per cercare l'elemento aumenterà logaritmicamente con la dimensione dell'array.
Allo stesso modo, l'ordine di complessità di altri algoritmi, come Algoritmi di ordinamento , Algoritmi grafici , E Algoritmi di programmazione dinamica dipende anche dal numero di operazioni che il programma esegue. L'ordine di complessità di questi algoritmi può essere espresso utilizzando Grande O notazione.
Diamo un'occhiata ad alcuni ordini comuni di complessità e ai loro algoritmi corrispondenti:
Ciò significa che l'algoritmo impiega una quantità di tempo costante, indipendentemente dalla dimensione dell'input. Ad esempio, l'accesso a un elemento in un array richiede O(1) time, poiché è possibile accedere all'elemento direttamente utilizzando il suo indice.
Ciò significa che il tempo impiegato dall'algoritmo aumenta logaritmicamente con la dimensione dell'input. Questo è comunemente visto in Algoritmi divide et impera Piace Ricerca binaria , che dividono l'input in parti più piccole per risolvere il problema.
Ciò significa che il tempo impiegato dall'algoritmo aumenta linearmente con la dimensione dell'input. Esempi di tali algoritmi sono Ricerca lineare E Ordinamento a bolle .
Ciò significa che il tempo impiegato dall'algoritmo aumenta di n moltiplicato per il logaritmo di n. Esempi di tali algoritmi sono Ordinamento rapido E Mergesort .
Ciò significa che il tempo impiegato dall'algoritmo aumenta quadraticamente con la dimensione dell'input. Esempi di tali algoritmi sono Ordinamento a bolle E Ordinamento per inserimento .
Ciò significa che il tempo impiegato dall'algoritmo raddoppia ad ogni aumento della dimensione dell'input. Questo è comunemente visto in Algoritmi ricorsivi come il Serie di Fibonacci .
È importante sapere che l'ordine di complessità fornisce solo un limite superiore al tempo impiegato dall'algoritmo. Il tempo effettivo impiegato potrebbe essere molto inferiore a questo limite, a seconda dei dati di input e dell'implementazione dell'algoritmo.
Nella programmazione C, l'ordine di complessità di un algoritmo può essere determinato analizzando il codice e contando il numero di operazioni eseguite. Ad esempio, se abbiamo un ciclo che itera attraverso un array di dimensione n, la complessità temporale del ciclo sarà SU) . Allo stesso modo, se abbiamo una funzione ricorsiva che chiama se stessa k volte, la complessità temporale della funzione sarà O(2^k) .
Per ottimizzare le prestazioni di un programma è importante scegliere algoritmi con un ordine di complessità inferiore. Ad esempio, se dobbiamo ordinare un array, dovremmo utilizzare un algoritmo di ordinamento con un ordine di complessità inferiore, come Ordinamento rapido O Mergesort , piuttosto che Ordinamento a bolle , che ha un ordine di complessità più elevato.
Analizzando l'ordine di complessità:
Per analizzare l'ordine di complessità di un algoritmo, dobbiamo determinare come cresce il tempo di esecuzione o l'utilizzo dello spazio all'aumentare della dimensione dell'input. Il metodo più comune per farlo è contare il numero di operazioni di base eseguite dall'algoritmo.
Un'operazione di base è un'operazione la cui esecuzione richiede una quantità costante di tempo, ad esempio la somma di due numeri o l'accesso a un elemento di un array. Contando il numero di operazioni di base eseguite dall'algoritmo in funzione della dimensione dell'input, possiamo determinarne l'ordine di complessità.
Ad esempio, considera la seguente funzione C che calcola la somma dei primi n interi:
Codice C:
int sum(int n) { int total = 0; for (int i = 1; i <= n; i++) { total +="i;" } return total; < pre> <p>In this function, the loop runs n times, and each iteration performs a constant amount of work (adding i to the total). Therefore, the number of basic operations performed by this algorithm is proportional to n, and its time complexity is <strong>O(n)</strong> .</p> <hr></=>