L'ordre de la complexitat és un terme utilitzat en informàtica per mesurar l'eficiència d'un algorisme o d'un programa. Es refereix a la quantitat de temps i recursos necessaris per resoldre un problema o realitzar una tasca. En programació, l'ordre de la complexitat s'expressa normalment en termes de Gran O notació, que dóna un límit superior dels requisits de temps o espai d'un algorisme. En aquest article, parlarem de l'ordre de la complexitat en el llenguatge de programació C i la seva importància.
Ordre de complexitat en el llenguatge de programació C:
En la programació en C, l'ordre de complexitat d'un algorisme depèn del nombre d'operacions realitzades pel programa. Per exemple, si tenim una matriu de mida n i volem cercar un element concret a la matriu, l'ordre de complexitat de l'algorisme dependrà del nombre d'elements de la matriu. Si realitzem a Cerca lineal a través de la matriu, serà l'ordre de la complexitat O(n) , el que significa que el temps necessari per buscar l'element augmentarà linealment amb la mida de la matriu. Si fem servir a Algorisme de cerca binària en canvi, serà l'Ordre de la Complexitat O(log n) , el que significa que el temps necessari per buscar l'element augmentarà logarítmicament amb la mida de la matriu.
De la mateixa manera, l'ordre de complexitat d'altres algorismes, com ara Algorismes d'ordenació , Algorismes gràfics , i Algorismes de programació dinàmica també depèn del nombre d'operacions que realitzi el programa. L'ordre de complexitat d'aquests algorismes es pot expressar utilitzant Gran O notació.
convertir cadena en char
Fem una ullada a alguns ordres comuns de complexitat i els seus algorismes corresponents:
Això vol dir que l'algorisme triga una quantitat de temps constant, independentment de la mida d'entrada. Per exemple, accedir a un element d'una matriu pren O(1) temps, ja que es pot accedir directament a l'element mitjançant el seu índex.
Això vol dir que el temps que pren l'algoritme augmenta logarítmicament amb la mida d'entrada. Això es veu habitualment a Algorismes de divideix i vencera M'agrada Cerca binària , que divideixen l'entrada en parts més petites per resoldre el problema.
Això vol dir que el temps que pren l'algorisme augmenta linealment amb la mida d'entrada. Alguns exemples d'aquests algorismes són Cerca lineal i Classificació de bombolles .
Això vol dir que el temps que triga l'algorisme augmenta per n multiplicat pel logaritme de n. Alguns exemples d'aquests algorismes són Classificació ràpida i Mergesort .
Això vol dir que el temps que pren l'algorisme augmenta quadràticament amb la mida d'entrada. Alguns exemples d'aquests algorismes són Classificació de bombolles i Ordenació d'inserció .
miniaplicació
Això significa que el temps que triga l'algorisme es duplica amb cada augment de la mida d'entrada. Això es veu habitualment a Algorismes recursius com el Sèrie de Fibonacci .
És important saber que l'ordre de complexitat només proporciona un límit superior del temps que triga l'algorisme. El temps real pot ser molt inferior a aquest límit, depenent de les dades d'entrada i de la implementació de l'algorisme.
En la programació en C, l'ordre de complexitat d'un algorisme es pot determinar analitzant el codi i comptant el nombre d'operacions realitzades. Per exemple, si tenim un bucle que itera a través d'una matriu de mida n, la complexitat temporal del bucle serà O(n) . De la mateixa manera, si tenim una funció recursiva que s'anomena k vegades, la complexitat temporal de la funció serà O(2^k) .
Per optimitzar el rendiment d'un programa, és important triar algorismes amb un ordre de complexitat inferior. Per exemple, si necessitem ordenar una matriu, hauríem d'utilitzar un algorisme d'ordenació amb un ordre inferior de complexitat, com ara Classificació ràpida o Mergesort , enlloc de Classificació de bombolles , que té un ordre de complexitat superior.
Anàlisi de l'ordre de complexitat:
Per analitzar l'ordre de complexitat d'un algorisme, hem de determinar com creix el seu temps d'execució o l'ús d'espai a mesura que augmenta la mida d'entrada. El mètode més comú per fer-ho és comptar el nombre d'operacions bàsiques realitzades per l'algorisme.
matriu en llenguatge c
Una operació bàsica és una operació que triga una quantitat de temps constant a realitzar-se, com ara afegir dos números o accedir a un element de matriu. Comptant el nombre d'operacions bàsiques realitzades per l'algorisme en funció de la mida d'entrada, podem determinar el seu ordre de complexitat.
Per exemple, considereu la següent funció C que calcula la suma dels n primers nombres enters:
Codi 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></=>