Molts estudiants es confonen mentre entenen el concepte de complexitat temporal, però en aquest article ho explicarem amb un exemple molt senzill.
P. Imagineu una aula de 100 alumnes en la qual vau donar el vostre bolígraf a una persona. Has de trobar aquest bolígraf sense saber a qui l'has donat.
Aquí hi ha algunes maneres de trobar el llapis i quin és l'ordre O.
- O (n 2 ): Vas a preguntar a la primera persona de la classe si té el bolígraf. A més, li preguntes a aquesta persona sobre les altres 99 persones de l'aula si tenen aquest bolígraf i així successivament,
Això és el que anomenem O(n2). - O(n): Anar i preguntar a cada alumne individualment és O(N).
- O(log n): Ara divideixo la classe en dos grups i després pregunto: És a l'esquerra o a la dreta de l'aula? Aleshores agafo aquest grup i el divideixo en dos i torno a preguntar, i així successivament. Repetiu el procés fins que us quedeu un estudiant que tingui el vostre bolígraf. Això és el que vols dir amb O (log n).
Potser hauria de fer:
- El O (n 2 ) cerques si només un alumne sap a quin alumne està amagat el bolígraf .
- El O(n) si un alumne tenia el bolígraf i només ells ho sabien .
- El O(log n) cerca si tots els alumnes ho sabien , però només em diria si endevinés el costat correcte.
El de sobre O -> es diu Gran - Oh que és una notació asimptòtica. N'hi ha d'altres Notacions asimptòtiques M'agrada theta i Omega .
NOTA: Ens interessa la taxa de creixement al llarg del temps pel que fa a les aportacions preses durant l'execució del programa.
La complexitat temporal d'un algorisme/codi és la mateixa que el temps d'execució/execució del codi?
La complexitat temporal d'un algorisme/codi és no igual al temps real necessari per executar un codi concret, però el nombre de vegades que s'executa una instrucció. Ho podem demostrar fent servir el comandament del temps .
Per exemple: Escriu codi en C/C++ o qualsevol altre llenguatge per trobar el màxim entre N nombres, on N varia entre 10, 100, 1000 i 10000. Per al sistema operatiu basat en Linux (Fedora o Ubuntu), utilitzeu les ordres següents:
importar escàner java
Per compilar el programa: programa gcc.c – o programa
Per executar el programa: temps ./programa
Obtindreu resultats sorprenents, és a dir:
- Per a N = 10: podeu obtenir 0,5 ms de temps,
- Per a N = 10.000: podeu obtenir 0,2 ms de temps.
- A més, obtindreu diferents temps en diferents màquines. Fins i tot si no obtindreu els mateixos horaris a la mateixa màquina per al mateix codi, el motiu d'això és la càrrega actual de la xarxa.
Per tant, podem dir que el El temps real necessari per executar el codi depèn de la màquina (tant si feu servir Pentium 1 o Pentium 5) i també considera la càrrega de la xarxa si la vostra màquina està a LAN/WAN.
Què s'entén per complexitat temporal d'un algorisme?
Ara, sorgeix la pregunta si la complexitat del temps no és el temps real necessari per executar el codi, llavors què és?
La resposta és:
En lloc de mesurar el temps real necessari per executar cada instrucció del codi, La complexitat temporal considera quantes vegades s'executa cada instrucció.
Exemple 1: Considereu el codi senzill a continuació imprimir Hola món
C++ #include using namespace std; int main() { cout << 'Hello World'; return 0; } // This code is contributed by vikash36905.> C #include int main() { printf('Hello World'); return 0; }> Java import java.io.*; class GFG { public static void main(String[] args) { System.out.print('Hello World'); } } // This code is contributed by vikash36905.> Python 3 print('Hello World') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code Console.WriteLine('Hello World'); } } // This code is contributed by lokesh> Javascript console.log('Hello World') // This code is contributed by nilha72xi.> Sortida
Hello World>
Complexitat temporal: En el codi anterior, Hello World només s'imprimeix una vegada a la pantalla.
Per tant, la complexitat del temps és constant: O(1) és a dir, cada vegada que es requereix una quantitat de temps constant per executar codi, independentment del sistema operatiu o de la configuració de la màquina que utilitzeu.
Espai Auxiliar : O(1)
Exemple 2:
tostring en javaC++
#include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i++) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by vikash36905.> C #include void main() { int i, n = 8; for (i = 1; i <= n; i++) { printf('Hello World !!!
'); } }> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { System.out.printf('Hello World !!!
'); } } } // This code is contributed by Rajput-Ji> Python 3 # Python code n = 8 for i in range(1, n + 1): print('Hello World !!!') # This code is contributed by lokesh> C# using System; public class GFG { public static void Main(String[] args) { int i, n = 8; for (i = 1; i <= n; i++) { Console.Write('Hello World !!!
'); } } } // This code contributed by Rajput-Ji> Javascript let i, n = 8; for (i = 1; i <= n; i++) { console.log('Hello World !!!'); }> Sortida
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complexitat temporal: Al codi anterior Hola món !!! només s'imprimeix n vegades a la pantalla, ja que el valor de n pot canviar.
Per tant, la complexitat del temps és lineal: O(n) és a dir, cada vegada, es requereix una quantitat de temps lineal per executar el codi.
Espai auxiliar: O(1)
Exemple 3:
C++ #include using namespace std; int main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include void main() { int i, n = 8; for (i = 1; i <= n; i=i*2) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java class GFG { public static void main(String[] args) { int i, n = 8; for (i = 1; i <= n; i=i*2) { System.out.println('Hello World !!!'); } } } // This code is contributed by Suruchi Kumari> Python 3 n = 8 # for (i = 1; i <= n; i=i*2) { for i in range(1, n+1, 2): print('Hello World !!!') # This code is contributed by akashish__> C# using System; public class GFG{ static public void Main (){ // Code int i, n = 8; for (i = 1; i <= n; i=i*2) { Console.Write('Hello World !!!
'); } } } // This code is contributed by lokeshmvs21.> Javascript for (i = 1; i <= 8; i=i*2) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Sortida
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complexitat temporal: O (log2(n))
Espai auxiliar: O(1)
Exemple 4:
C++ #include #include using namespace std; int main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { cout << 'Hello World !!!
'; } return 0; } // This code is contributed by Suruchi Kumari> C #include #include void main() { int i, n = 8; for (i = 2; i <= n; i=pow(i,2)) { printf('Hello World !!!
'); } } // This code is contributed by Suruchi Kumari> Java import java.lang.Math; class GFG { public static void main(String args[]){ int i, n = 8; for (i = 2; i <= n; i=(int)Math.pow(i,2)) { System.out.println('Hello World !!!'); } } }> Python 3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hola món!!!') i *= i # Aquest codi és aportat per akashish__> C# using System; using System.Collections.Generic; public class GFG { static public void Main() { int i, n = 8; for (i = 2; i <= n; i = (int)Math.Pow(i, 2)) { Console.WriteLine('Hello World !!!'); } } } // This code is contributed by akashish__> Javascript for (let i = 2; i <= 8; i=Math.pow(i,2)) { console.log('Hello World !!!'); } // This code is contributed by nilha7xi.> Sortida
Hello World !!! Hello World !!!>
Complexitat temporal: O(log(log n))
Espai auxiliar: O(1)
Com trobar la complexitat temporal d'un algorisme?
Vegem ara alguns altres exemples i el procés per trobar la complexitat temporal d'un algorisme:
Exemple: Considerem un model de màquina que té les especificacions següents:
- Processador únic
- 32 bits
- Execució seqüencial
- 1 unitat de temps per a operacions aritmètiques i lògiques
- 1 unitat de temps per a les declaracions d'assignació i devolució
Q1. Trobeu la suma de 2 nombres a la màquina anterior:
Per a qualsevol màquina, el pseudocodi per afegir dos números serà una cosa així:
C++ // Pseudocode : Sum(a, b) { return a + b } #include using namespace std; int sum(int a,int b) { return a+b; } int main() { int a = 5, b = 6; cout< C Pseudocode : Sum(a, b) { return a + b }> Java // Pseudocode : Sum(a, b) { return a + b } import java.io.*; class GFG { public static int sum(int a, int b) { return a + b; } public static void main(String[] args) { int a = 5, b = 6; System.out.println(sum(a, b)); } } // This code is contributed by akashish__> Python 3 # Pseudocode : Sum(a, b) { return a + b } a = 5 b = 6 def sum(a,b): return a+b # function call print(sum(a,b))> C# // Pseudocode : Sum(a, b) { return a + b } using System; public class GFG { public static int sum(int a, int b) { return a + b; } static public void Main() { int a = 5, b = 6; Console.WriteLine(sum(a, b)); } } // This code is contributed by akashish__> Javascript // Pseudocode : Sum(a, b) { return a + b } function sum(a, b) { return a + b; } let a = 5, b = 6; console.log(sum(a, b)); // This code is contributed by akashish__> Sortida
11>
Complexitat temporal:
- El codi anterior trigarà 2 unitats de temps (constant):
- un per a operacions aritmètiques i
- un per tornar. (segons les convencions anteriors).
- Per tant, cost total per realitzar l'operació de suma ( ) = 1 + 1 = 2
- Complexitat temporal = O(2) = O(1) , ja que 2 és constant
Espai auxiliar: O(1)
P2. Troba la suma de tots els elements d'una llista/matriu
El pseudocodi per fer-ho es pot donar com:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->matriu i // n->nombre d'elements de la matriu { int suma = 0; per (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } int main() { int A[] = { 5, 6, 1, 2 }; int n = sizeof(A) / sizeof(A[0]); cout << list_Sum(A, n); return 0; } // This code is contributed by akashish__> C Pseudocode : list_Sum(A, n) // A->matriu i // n->nombre d'elements de la matriu { suma = 0 per i = 0 a n-1 suma = suma + A[i] retorna suma }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->matriu i // n->nombre d'elements de la matriu { int suma = 0; per (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } public static void main(String[] args) { int[] A = { 5, 6, 1, 2 }; int n = A.length; System.out.println(list_Sum(A, n)); } } // This code is contributed by lokeshmvs21.> Python 3 # A function to calculate the sum of the elements in an array def list_sum(A, n): sum = 0 for i in range(n): sum += A[i] return sum # A sample array A = [5, 6, 1, 2] # Finding the number of elements in the array n = len(A) # Call the function and print the result print(list_sum(A, n))>
C# using System; public class GFG { public static int list_Sum(int[] A, int n) // A->matriu i // n->nombre d'elements de la matriu { int suma = 0; per (int i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } static public void Main() { int[] A = { 5, 6, 1, 2 }; int n = A.Length; Console.WriteLine(list_Sum(A, n)); } } // This code is contributed by akashish__> Javascript function list_Sum(A, n) // A->matriu i // n->nombre d'elements de la matriu { Let sum = 0; per (sigui i = 0; i<= n - 1; i++) { sum = sum + A[i]; } return sum; } let A = [ 5, 6, 1, 2 ]; let n = A.length; console.log(list_Sum(A, n)); // This code is contributed by akashish__> Sortida
14>
Per entendre la complexitat temporal del codi anterior, vegem quant de temps trigarà cada declaració:
int list_Sum(int A[], int n) { int sum = 0; // cost=1 no of times=1 for(int i=0; i C Pseudocode : list_Sum(A, n) { total =0 // cost=1 no of times=1 for i=0 to n-1 // cost=2 no of times=n+1 (+1 for the end false condition) sum = sum + A[i] // cost=2 no of times=n return sum // cost=1 no of times=1 }> Java public class ListSum { // Function to calculate the sum of elements in an array static int listSum(int[] A, int n) { int sum = 0; // Cost = 1, executed 1 time for (int i = 0; i < n; i++) { // Cost = 2, executed n+1 times (+1 for // the end false condition) sum = sum + A[i]; // Cost = 2, executed n times } return sum; // Cost = 1, executed 1 time } // Main method for testing public static void main(String[] args) { int[] array = {1, 2, 3, 4, 5}; int length = array.length; int result = listSum(array, length); System.out.println('Sum: ' + result); } }> Python 3 def list_sum(A): sum = 0 for i in range(len(A)): sum = sum + A[i] return sum>
C# using System; class Program { // Function to calculate the sum of elements in a list static int ListSum(int[] A) { int sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (int i = 0; i < A.Length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Driver code static void Main() { // Example usage int[] array = { 1, 2, 3, 4, 5 }; int result = ListSum(array); Console.WriteLine(result); } }> Javascript function listSum(A) { let sum = 0; // Initialize sum to 0 // Loop to iterate through the array elements for (let i = 0; i < A.length; i++) { sum = sum + A[i]; // Accumulate the sum } return sum; // Return the calculated sum } // Example usage let array = [1, 2, 3, 4, 5]; let result = listSum(array); console.log(result);> Per tant, el cost total per realitzar l'operació suma
Suma=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Per tant, la complexitat temporal del codi anterior és O(n)
P3. Troba la suma de tots els elements d'una matriu
Per a aquesta, la complexitat és una equació polinòmica (equació quadrada per a una matriu quadrada)
- Matriu de mida n*n => Tsum = a.n 2 + b.n + c
- Com que Tsum és de l'ordre de n2, per tant Complexitat temporal = O(n 2 )
#include using namespace std; int main() { int n = 3; int m = 3; int arr[][3] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } cout << sum << endl; return 0; } // contributed by akashish__> Java /*package whatever //do not write package name here */ import java.io.*; class GFG { public static void main(String[] args) { int n = 3; int m = 3; int arr[][] = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } System.out.println(sum); } } // akashish__> Python 3 n = 3 m = 3 arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]] sum = 0 # Iterating over all 1-D arrays in 2-D array for i in range(n): # Printing all elements in ith 1-D array for j in range(m): # Printing jth element of ith row sum += arr[i][j] print(sum) # This code id contributed by shivhack999>
C# using System; class MainClass { static void Main(string[] args) { int n = 3; int m = 3; int[, ] arr = { { 3, 2, 7 }, { 2, 6, 8 }, { 5, 1, 9 } }; int sum = 0; // Iterating over all 1-D arrays in 2-D array for (int i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (int j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i, j]; } } Console.WriteLine(sum); } }> Javascript let n = 3; let m = 3; let arr = [[3, 2, 7], [2, 6, 8], [5, 1, 9]]; let sum = 0; // Iterating over all 1-D arrays in 2-D array for (let i = 0; i < n; i++) { // Printing all elements in ith 1-D array for (let j = 0; j < m; j++) { // Printing jth element of ith row sum += arr[i][j]; } } console.log(sum);> Sortida
43>
Complexitat temporal: O(n*m)
El programa itera per tots els elements de la matriu 2D mitjançant dos bucles imbricats. El bucle exterior itera n vegades i el bucle intern itera m vegades per a cada iteració del bucle exterior. Per tant, la complexitat temporal del programa és O(n*m).
Espai auxiliar: O(n*m)
El programa utilitza una quantitat fixa d'espai auxiliar per emmagatzemar la matriu 2D i unes quantes variables senceres. L'espai necessari per a la matriu 2D és nm nombres enters. El programa també utilitza una única variable entera per emmagatzemar la suma dels elements. Per tant, la complexitat espacial auxiliar del programa és O(nm + 1), que es simplifica a O(n*m).
itera el mapa en java
En conclusió, la complexitat temporal del programa és O(nm), i la complexitat de l'espai auxiliar també és O(nm).
Així, dels exemples anteriors, podem concloure que el temps d'execució augmenta amb el tipus d'operacions que fem utilitzant les entrades.
Com comparar algorismes?
Per comparar algorismes, definim algunes mesures objectives:
- Temps d'execució: No és una bona mesura, ja que els temps d'execució són específics d'un ordinador en particular.
- Nombre d'instruccions executades: No és una bona mesura, ja que el nombre d'instruccions varia segons el llenguatge de programació i l'estil del programador individual.
- Solució ideal: Suposem que expressem el temps d'execució d'un algorisme donat en funció de la mida d'entrada n (és a dir, f(n)) i comparem aquestes diferents funcions corresponents als temps d'execució. Aquest tipus de comparació és independent del temps de la màquina, de l'estil de programació, etc.
Per tant, es pot utilitzar una solució ideal per comparar algorismes.
Articles relacionats:
- Complexitat temporal i complexitat espacial
- Anàlisi d'algorismes | Conjunt 1 (anàlisi asimptòtica)
- Anàlisi d'algorismes | Set 2 (Pitjor, Mitjana i Millor Cas)
- Anàlisi d'algorismes | Set 3 (notacions asimptòtiques)
- Anàlisi d'algorismes | Set 4 (anàlisi de bucles)
- Anàlisi de l'algoritme | Conjunt 5 (introducció a l'anàlisi amortitzada)
- Problemes diversos de complexitat temporal
- Preguntes pràctiques sobre l'anàlisi de la complexitat temporal
- Conèixer la complexitat de la programació competitiva