Molti studenti si confondono nel comprendere il concetto di complessità temporale, ma in questo articolo lo spiegheremo con un esempio molto semplice.
D. Immagina una classe di 100 studenti in cui hai dato la tua penna a una persona. Devi trovare quella penna senza sapere a chi l'hai data.
Ecco alcuni modi per trovare la penna e qual è l'ordine O.
- SU 2 ): Vai a chiedere al primo della classe se ha la penna. Inoltre, chiedi a questa persona delle altre 99 persone in classe se hanno quella penna e così via,
Questo è ciò che chiamiamo O(n2). - SU): Andare a chiedere a ogni studente individualmente è O(N).
- O(log n): Ora divido la classe in due gruppi, poi chiedo: è sul lato sinistro o sul lato destro dell'aula? Poi prendo quel gruppo e lo divido in due e chiedo di nuovo, e così via. Ripeti il processo finché non ti rimane uno studente con la tua penna. Questo è ciò che intendi con O(log n).
Potrei aver bisogno di fare:
- IL SU 2 ) cerca se solo uno studente sa su quale studente è nascosta la penna .
- IL SU) Se uno studente aveva la penna e solo loro lo sapevano .
- IL O(log n) cerca se tutti gli studenti lo sapevano , ma me lo direbbe solo se indovinassi il lato giusto.
Quanto sopra O -> si chiama Grande – Oh che è una notazione asintotica. Ci sono altri notazioni asintotiche Piace theta E Omega .
NOTA: A noi interessa il tasso di crescita nel tempo rispetto agli input presi durante l’esecuzione del programma.
La complessità temporale di un algoritmo/codice è uguale al tempo di esecuzione/esecuzione del codice?
La complessità temporale di un algoritmo/codice è non uguale al tempo effettivo richiesto per eseguire un particolare codice, ma al numero di volte in cui viene eseguita un'istruzione. Possiamo dimostrarlo utilizzando il metodo comando temporale .
Per esempio: Scrivi il codice in C/C++ o qualsiasi altro linguaggio per trovare il massimo tra N numeri, dove N varia da 10, 100, 1000 e 10000. Per il sistema operativo basato su Linux (Fedora o Ubuntu), utilizza i comandi seguenti:
sdlc
Per compilare il programma: programma gcc.c – o programma
Per eseguire il programma: tempo ./programma
Otterrai risultati sorprendenti, ad esempio:
- Per N = 10: potresti ottenere un tempo di 0,5 ms,
- Per N = 10.000: potresti ottenere un tempo di 0,2 ms.
- Inoltre, otterrai tempi diversi su macchine diverse. Anche se non otterrai gli stessi tempi sulla stessa macchina per lo stesso codice, il motivo è l'attuale carico di rete.
Quindi, possiamo dire che il il tempo effettivo necessario per eseguire il codice dipende dalla macchina (se si utilizza Pentium 1 o Pentium 5) e considera anche il carico di rete se la macchina è in LAN/WAN.
Cosa si intende per complessità temporale di un algoritmo?
Ora, sorge la domanda: se la complessità temporale non è il tempo effettivo richiesto per eseguire il codice, di cosa si tratta?
La risposta è:
Invece di misurare il tempo effettivo richiesto per eseguire ciascuna istruzione nel codice, La complessità temporale considera quante volte viene eseguita ciascuna istruzione.
Esempio 1: Considera il semplice codice seguente per stampa Ciao mondo
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; }> Giava 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.> Produzione
Hello World>
Complessità temporale: Nel codice sopra Hello World viene stampato solo una volta sullo schermo.
Quindi, la complessità temporale è costante: O(1) cioè ogni volta che è necessario un tempo costante per eseguire il codice, indipendentemente dal sistema operativo o dalla configurazione della macchina in uso.
Spazio ausiliario : O(1)
Esempio 2:
impostazioni del browser webC++
#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 !!!
'); } }> Giava 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 !!!'); }> Produzione
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complessità temporale: Nel codice sopra Ciao Mondo!!! viene solo stampato n volte sullo schermo, poiché il valore di n può cambiare.
Quindi, la complessità temporale è lineare: O(n) cioè ogni volta è necessaria una quantità lineare di tempo per eseguire il codice.
Spazio ausiliario: O(1)
Esempio 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> Giava 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.> Produzione
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>
Complessità temporale: O(log2(N))
Spazio ausiliario: O(1)
Esempio 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> Giava 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 # Questo codice è fornito da 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.> Produzione
Hello World !!! Hello World !!!>
Complessità temporale: O(log(log n))
Spazio ausiliario: O(1)
Come trovare la complessità temporale di un algoritmo?
Vediamo ora qualche altro esempio e il processo per trovare la complessità temporale di un algoritmo:
Esempio: Consideriamo un modello di macchina che abbia le seguenti specifiche:
- Processore singolo
- 32 bit
- Esecuzione sequenziale
- 1 unità di tempo per operazioni aritmetiche e logiche
- 1 unità di tempo per le dichiarazioni di assegnazione e restituzione
Q1. Trova la somma di 2 numeri sulla macchina sopra:
Per qualsiasi macchina, lo pseudocodice per aggiungere due numeri sarà qualcosa del genere:
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 }> Giava // 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__> Produzione
11>
Complessità temporale:
- Il codice sopra richiederà 2 unità di tempo (costanti):
- uno per le operazioni aritmetiche e
- uno per il reso. (secondo le convenzioni di cui sopra).
- Pertanto il costo totale per eseguire l'operazione di somma ( ) = 1 + 1 = 2
- Complessità temporale = O(2) = O(1) , poiché 2 è costante
Spazio ausiliario: O(1)
Q2. Trova la somma di tutti gli elementi di una lista/array
Lo pseudocodice per farlo può essere dato come:
C++ #include using namespace std; int list_Sum(int A[], int n) // A->array e // n->numero di elementi nell'array { int sum = 0; for (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->array e // n->numero di elementi nell'array { somma = 0 for i = 0 a n-1 somma = somma + A[i] return somma }> Giava // Java code for the above approach import java.io.*; class GFG { static int list_Sum(int[] A, int n) // A->array e // n->numero di elementi nell'array { int sum = 0; for (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->array e // n->numero di elementi nell'array { int sum = 0; for (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->array e // n->numero di elementi nell'array { let sum = 0; per (sia 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__> Produzione
14>
Per comprendere la complessità temporale del codice sopra, vediamo quanto tempo impiegherà ciascuna istruzione:
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 }> Giava 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);> Pertanto il costo totale per eseguire l'operazione di somma
Somma=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)
Pertanto, la complessità temporale del codice di cui sopra è SU)
Q3. Trova la somma di tutti gli elementi di una matrice
Per questo, la complessità è un'equazione polinomiale (equazione quadratica per una matrice quadrata)
- Matrice di dimensione n*n => Tsum = n.a 2 + b.n + c
- Poiché Tsum è dell'ordine del n2, Perciò Complessità temporale = 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__> Giava /*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);> Produzione
43>
Complessità temporale: O(n*m)
Il programma scorre tutti gli elementi nell'array 2D utilizzando due cicli nidificati. Il ciclo esterno ripete n volte e il ciclo interno ripete m volte per ogni iterazione del ciclo esterno. Pertanto, la complessità temporale del programma è O(n*m).
Spazio ausiliario: O(n*m)
Il programma utilizza una quantità fissa di spazio ausiliario per memorizzare l'array 2D e alcune variabili intere. Lo spazio richiesto per l'array 2D è di nm interi. Il programma utilizza anche una singola variabile intera per memorizzare la somma degli elementi. Pertanto, la complessità dello spazio ausiliario del programma è O(nm + 1), che si semplifica in O(n*m).
jquery un clic
In conclusione, la complessità temporale del programma è O(nm), e anche la complessità spaziale ausiliaria è O(nm).
Quindi dagli esempi precedenti possiamo concludere che il tempo di esecuzione aumenta con il tipo di operazioni che facciamo utilizzando gli input.
Come confrontare gli algoritmi?
Per confrontare gli algoritmi, definiamo alcune misure oggettive:
- Tempi di esecuzione: Non è una buona misura poiché i tempi di esecuzione sono specifici per un particolare computer.
- Il numero di istruzioni eseguite: Non è una buona misura, poiché il numero di istruzioni varia a seconda del linguaggio di programmazione e dello stile del singolo programmatore.
- Soluzione ideale: Supponiamo di esprimere il tempo di esecuzione di un dato algoritmo in funzione della dimensione dell'input n (cioè f(n)) e confrontare queste diverse funzioni corrispondenti ai tempi di esecuzione. Questo tipo di confronto è indipendente dal tempo macchina, dallo stile di programmazione, ecc.
Pertanto, è possibile utilizzare una soluzione ideale per confrontare gli algoritmi.
Articoli Correlati:
- Complessità temporale e complessità spaziale
- Analisi degli algoritmi | Set 1 (analisi asintotica)
- Analisi degli algoritmi | Set 2 (casi peggiore, medio e migliore)
- Analisi degli algoritmi | Set 3 (notazioni asintotiche)
- Analisi degli algoritmi | Set 4 (Analisi dei loop)
- Analisi dell'algoritmo | Set 5 (Introduzione all'analisi ammortizzata)
- Problemi vari di complessità temporale
- Domande pratiche sull'analisi della complessità temporale
- Conoscere la complessità della programmazione competitiva