Mulți studenți devin confuzi în timp ce înțeleg conceptul de complexitate a timpului, dar în acest articol îl vom explica cu un exemplu foarte simplu.
Î. Imaginează-ți o sală de clasă de 100 de elevi în care ai dat stiloul tău unei singure persoane. Trebuie să găsești acel stilou fără să știi cui i-ai dat.
Iată câteva modalități de a găsi stiloul și care este ordinea O.
- Pe 2 ): Te duci și îl întrebi pe prima persoană din clasă dacă are stiloul. De asemenea, întrebați această persoană despre celelalte 99 de persoane din clasă dacă au acel stilou și așa mai departe,
Acesta este ceea ce numim O(n2). - Pe): A merge și a întreba fiecare elev individual este O(N).
- O(log n): Acum împart clasa în două grupuri, apoi întreb: este în partea stângă sau în partea dreaptă a clasei? Apoi iau acel grup și îl împart în două și întreb din nou și așa mai departe. Repetați procesul până când rămâneți cu un student care are stiloul dvs. Aceasta este ceea ce vrei să spui prin O(log n).
S-ar putea să trebuiască să fac:
- The Pe 2 ) caută dacă doar un elev știe pe care elev este ascuns stiloul .
- The Pe) dacă un elev avea stiloul și numai ei îl știau .
- The O(log n) cauta daca toti elevii stiau , dar mi-ar spune doar dacă aș ghici partea dreaptă.
Cele de mai sus O -> se numește Mare – Oh care este o notație asimptotică. Sunt altele notații asimptotice ca teta și Omega .
NOTĂ: Suntem interesați de rata de creștere în timp în ceea ce privește inputurile luate în timpul execuției programului.
Complexitatea de timp a unui algoritm/cod este aceeași cu timpul de rulare/execuție a codului?
Complexitatea de timp a unui algoritm/cod este nu egal cu timpul efectiv necesar pentru a executa un anumit cod, dar numărul de ori se execută o instrucțiune. Putem demonstra acest lucru folosind comanda timpului .
De exemplu: Scrieți codul în C/C++ sau orice altă limbă pentru a găsi maximul dintre N numere, unde N variază de la 10, 100, 1000 și 10000. Pentru sistemul de operare bazat pe Linux (Fedora sau Ubuntu), utilizați comenzile de mai jos:
listarea java
Pentru a compila programul: program gcc.c – o program
Pentru a executa programul: timp ./program
Veți obține rezultate surprinzătoare și anume:
- Pentru N = 10: puteți obține 0,5 ms de timp,
- Pentru N = 10.000: puteți obține 0,2 ms de timp.
- De asemenea, veți obține timpi diferite pe diferite mașini. Chiar dacă nu veți obține aceleași timpi pe aceeași mașină pentru același cod, motivul din spatele acestuia este încărcarea actuală a rețelei.
Deci, putem spune că timpul real necesar pentru executarea codului depinde de mașină (indiferent dacă utilizați Pentium 1 sau Pentium 5) și, de asemenea, ia în considerare încărcarea rețelei dacă mașina dvs. este în LAN/WAN.
Ce se înțelege prin complexitatea temporală a unui algoritm?
Acum, se pune întrebarea dacă complexitatea timpului nu este timpul efectiv necesar pentru a executa codul, atunci ce este?
Raspunsul este:
În loc să măsoare timpul real necesar pentru executarea fiecărei instrucțiuni din cod, Time Complexity ia în considerare de câte ori se execută fiecare instrucțiune.
Exemplul 1: Luați în considerare codul simplu de mai jos pentru a tipări Bună lume
pysparkC++
#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.> Python3 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.> Ieșire
Hello World>
Complexitatea timpului: În codul de mai sus, Hello World este tipărit o singură dată pe ecran.
Deci, complexitatea timpului este constantă: O(1) adică de fiecare dată când este necesară o perioadă constantă de timp pentru a executa codul, indiferent de sistemul de operare sau de configurațiile de mașină pe care le utilizați.
Spațiu auxiliar : O(1)
Exemplul 2:
C++ #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> Python3 # 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 !!!'); }> Ieșire
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complexitatea timpului: În codul de mai sus Hello World!!! este tipărită numai de n ori pe ecran, deoarece valoarea lui n se poate modifica.
Deci, complexitatea timpului este liniar: O(n) adică de fiecare dată, este necesară o perioadă liniară de timp pentru a executa codul.
Spațiu auxiliar: O(1)
Exemplul 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> Python3 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.> Ieșire
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complexitatea timpului: O (log2(n))
Spațiu auxiliar: O(1)
Exemplul 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 !!!'); } } }> Python3 n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # Acest cod este contribuit de 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.> Ieșire
Hello World !!! Hello World !!!>
Complexitatea timpului: O(log(log n))
Spațiu auxiliar: O(1)
Cum să găsiți complexitatea timpului a unui algoritm?
Acum să vedem câteva alte exemple și procesul de găsire a complexității în timp a unui algoritm:
Exemplu: Să luăm în considerare un model de mașină care are următoarele specificații:
- Un singur procesor
- 32 de biți
- Execuție secvențială
- 1 unitate de timp pentru operații aritmetice și logice
- 1 unitate de timp pentru extrasele de atribuire și returnare
Î1. Găsiți suma a 2 numere pe mașina de mai sus:
Pentru orice mașină, pseudocodul pentru a adăuga două numere va fi cam așa:
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__> Python3 # 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__> Ieșire
11>
Complexitatea timpului:
- Codul de mai sus va dura 2 unități de timp (constante):
- unul pentru operaţii aritmetice şi
- unul pentru întoarcere. (conform convențiilor de mai sus).
- Prin urmare, costul total pentru efectuarea operațiunii de sumă ( ) = 1 + 1 = 2
- Complexitatea timpului = O(2) = O(1) , deoarece 2 este constant
Spațiu auxiliar: O(1)
Q2. Găsiți suma tuturor elementelor unei liste/matrice
Pseudocodul pentru a face acest lucru poate fi dat ca:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->matrice și // n->număr de elemente din matrice { int sum = 0; pentru (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->matrice și // n->numărul de elemente din matrice { sumă = 0 pentru i = 0 până la n-1 sumă = sumă + A[i] returnează sumă }> Java // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->matrice și // n->număr de elemente din matrice { int sum = 0; pentru (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.> Python3 # 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->matrice și // n->număr de elemente din matrice { int sum = 0; pentru (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->matrice și // n->număr de elemente din matrice { let sum = 0; pentru (fie 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__> Ieșire
14>
Pentru a înțelege complexitatea în timp a codului de mai sus, să vedem cât timp va dura fiecare declarație:
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); } }> Python3 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);> Prin urmare, costul total pentru efectuarea operațiunii de sumă
Suma=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Prin urmare, complexitatea de timp a codului de mai sus este Pe)
Q3. Aflați suma tuturor elementelor unei matrice
Pentru aceasta, complexitatea este o ecuație polinomială (ecuație pătratică pentru o matrice pătrată)
fișier .tif
- Matrice de mărime n*n => Tsum = a.n 2 + b.n + c
- Deoarece Tsum este de ordinul lui n2, prin urmare Complexitatea timpului = 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__> Python3 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);> Ieșire
43>
Complexitatea timpului: O(n*m)
Programul iterează prin toate elementele din matricea 2D folosind două bucle imbricate. Bucla exterioară iterează de n ori, iar bucla interioară iterează de m ori pentru fiecare iterație a buclei exterioare. Prin urmare, complexitatea de timp a programului este O(n*m).
Spațiu auxiliar: O(n*m)
Programul folosește o cantitate fixă de spațiu auxiliar pentru a stoca matricea 2D și câteva variabile întregi. Spațiul necesar pentru matricea 2D este de nm numere întregi. Programul folosește, de asemenea, o singură variabilă întreagă pentru a stoca suma elementelor. Prin urmare, complexitatea spațiului auxiliar al programului este O(nm + 1), ceea ce se simplifică la O(n*m).
În concluzie, complexitatea în timp a programului este O(nm), iar complexitatea spațiului auxiliar este tot O(nm).
Deci, din exemplele de mai sus, putem concluziona că timpul de execuție crește odată cu tipul de operații pe care le facem folosind intrările.
Cum se compară algoritmii?
Pentru a compara algoritmii, să definim câteva măsuri obiective:
- Timpi de executie: Nu este o măsură bună, deoarece timpii de execuție sunt specifici unui anumit computer.
- Numărul de instrucțiuni executate: Nu este o măsură bună, deoarece numărul de instrucțiuni variază în funcție de limbajul de programare, precum și de stilul programatorului individual.
- Solutia ideala: Să presupunem că exprimăm timpul de rulare al unui algoritm dat ca o funcție a mărimii de intrare n (adică f(n)) și comparăm aceste funcții diferite corespunzătoare timpilor de rulare. Acest tip de comparație este independent de timpul mașinii, stilul de programare etc.
Prin urmare, o soluție ideală poate fi utilizată pentru a compara algoritmi.
Articole similare:
- Complexitatea timpului și complexitatea spațiului
- Analiza algoritmilor | Setul 1 (Analiza asimptotică)
- Analiza algoritmilor | Setul 2 (Cel mai rău, mediu și cel mai bun caz)
- Analiza algoritmilor | Setul 3 (notații asimptotice)
- Analiza algoritmilor | Setul 4 (Analiza buclelor)
- Analiza algoritmului | Setul 5 (introducere în analiza amortizată)
- Probleme diverse ale complexității timpului
- Întrebări practice privind analiza complexității timpului
- Cunoașterea complexității în programarea competitivă