logo

TechCodeview

Comprendre la complexité temporelle avec des exemples simples

De nombreux étudiants sont confus lorsqu'ils comprennent le concept de complexité temporelle, mais dans cet article, nous allons l'expliquer avec un exemple très simple.

Q. Imaginez une classe de 100 élèves dans laquelle vous donnez votre stylo à une personne. Vous devez retrouver ce stylo sans savoir à qui vous l’avez donné.



Voici quelques façons de trouver le stylo et quel est l'ordre O.

  • Sur 2 ) : Vous allez demander au premier de la classe s’il a le stylo. De plus, vous demandez à cette personne si les 99 autres personnes de la classe ont ce stylo, etc.
    C'est ce que nous appelons O(n2).
  • Sur): Aller demander à chaque élève individuellement est O(N).
  • O(log n): Maintenant, je divise la classe en deux groupes, puis je demande : est-ce du côté gauche ou du côté droit de la classe ? Ensuite, je prends ce groupe, je le divise en deux et je demande à nouveau, et ainsi de suite. Répétez le processus jusqu'à ce qu'il ne vous reste plus qu'un élève qui a votre stylo. C'est ce que vous entendez par O(log n).

Je devrai peut-être faire :

  • Le Sur 2 ) recherche si un seul élève sait sur quel élève le stylo est caché .
  • Le Sur) si un élève avait le stylo et lui seul le savait .
  • Le O (log n) chercher si tous les étudiants savaient , mais je ne me le dirais que si je devinais le bon côté.

Ci-dessus Ô -> s'appelle Gros – Oh qui est une notation asymptotique. Il y en a d'autres notations asymptotiques comme thêta et Oméga .



NOTE: Nous nous intéressons au taux de croissance dans le temps par rapport aux intrants pris lors de l'exécution du programme.

La complexité temporelle d'un algorithme/code est-elle la même que le temps d'exécution/d'exécution du code ?

La complexité temporelle d'un algorithme/code est pas égal au temps réel requis pour exécuter un code particulier, mais au nombre de fois qu'une instruction s'exécute. Nous pouvons le prouver en utilisant le commande temporelle .

Par exemple: Écrivez du code en C/C++ ou dans tout autre langage pour trouver le maximum entre N nombres, où N varie de 10, 100, 1 000 et 10 000. Pour le système d'exploitation basé sur Linux (Fedora ou Ubuntu), utilisez les commandes ci-dessous :



couleurs Java

Pour compiler le programme : programme gcc.c – o programme
Pour exécuter le programme : heure ./programme

Vous obtiendrez des résultats surprenants, à savoir :

  • Pour N = 10 : vous pouvez obtenir un temps de 0,5 ms,
  • Pour N = 10 000 : vous pouvez obtenir un temps de 0,2 ms.
  • De plus, vous obtiendrez des timings différents sur différentes machines. Même si vous n’obtiendrez pas les mêmes timings sur la même machine pour le même code, la raison en est la charge actuelle du réseau.

On peut donc dire que le le temps réel requis pour exécuter le code dépend de la machine (que vous utilisiez un Pentium 1 ou un Pentium 5) et prend également en compte la charge du réseau si votre machine est en LAN/WAN.

Qu’entend-on par complexité temporelle d’un algorithme ?

Maintenant, la question se pose : si la complexité temporelle n’est pas le temps réel nécessaire pour exécuter le code, alors de quoi s’agit-il ?

La réponse est:

Au lieu de mesurer le temps réel requis pour exécuter chaque instruction du code, La complexité temporelle prend en compte le nombre de fois où chaque instruction est exécutée.

Exemple 1: Considérez le code simple ci-dessous pour imprimer Bonjour tout le monde

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.>
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.>
Sortir 
Hello World>

Complexité temporelle : Dans le code ci-dessus, Hello World n'est imprimé qu'une seule fois à l'écran.
La complexité temporelle est donc constante : O(1) c'est-à-dire qu'à chaque fois, un temps constant est nécessaire pour exécuter du code, quel que soit le système d'exploitation ou les configurations de machine que vous utilisez.
Espace auxiliaire :O(1)

Exemple 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 !!!');  }>
Sortir 
Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Complexité temporelle : Dans le code ci-dessus Hello World !!! est imprimé uniquement n fois à l'écran, car la valeur de n peut changer.
La complexité temporelle est donc linéaire : O(n) c'est-à-dire qu'à chaque fois, une quantité de temps linéaire est nécessaire pour exécuter le code.
Espace auxiliaire : 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>
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.>
Sortir 
Hello World !!! Hello World !!! Hello World !!! Hello World !!!>

Complexité temporelle : O(journal2(n))
Espace auxiliaire : 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 !!!');  }  }  }>
Python3 
n = 8 i = 2 for j in range(2,n+1): if(i>= n): break print('Hello World !!!') i *= i # Ce code est contribué par 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.>
Sortir 
Hello World !!! Hello World !!!>

Complexité temporelle : O(log(log n))
Espace auxiliaire : O(1)

Comment trouver la complexité temporelle d’un algorithme ?

Voyons maintenant quelques autres exemples et le processus pour trouver la complexité temporelle d'un algorithme :

Exemple: Considérons un modèle de machine qui présente les spécifications suivantes :

  • Processeur unique
  • 32 bits
  • Exécution séquentielle
  • 1 unité de temps pour les opérations arithmétiques et logiques
  • 1 unité de temps pour les déclarations d'affectation et de retour

T1. Trouvez la somme de 2 nombres sur la machine ci-dessus :

Pour n’importe quelle machine, le pseudocode pour ajouter deux nombres ressemblera à ceci :

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__>
Sortir 
11>

Complexité temporelle :

java mathématiques
  • Le code ci-dessus prendra 2 unités de temps (constant) :
    • un pour les opérations arithmétiques et
    • un pour le retour. (selon les conventions ci-dessus).
  • Par conséquent, le coût total pour effectuer l’opération de somme ( ) = 1 + 1 = 2
  • Complexité temporelle = O(2) = O(1) , puisque 2 est constant

Espace auxiliaire : O(1)

Q2. Trouver la somme de tous les éléments d'une liste/d'un tableau

Le pseudocode pour ce faire peut être donné comme suit :

C++ 
#include  using namespace std; int list_Sum(int A[], int n)   // A->tableau et // n->nombre d'éléments dans le tableau { int sum = 0;  pour (int je = 0; je<= 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->tableau et // n->nombre d'éléments dans le tableau { somme = 0 pour i = 0 à n-1 somme = somme + A[i] return sum }>
Java 
// Java code for the above approach import java.io.*; class GFG {  static int list_Sum(int[] A, int n)  // A->tableau et // n->nombre d'éléments dans le tableau { int sum = 0;  pour (int je = 0; je<= 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->tableau et // n->nombre d'éléments dans le tableau { int sum = 0;  pour (int je = 0; je<= 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->tableau et // n->nombre d'éléments dans le tableau { let sum = 0;  pour (soit 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__>
Sortir 
14>


Pour comprendre la complexité temporelle du code ci-dessus, voyons combien de temps prendra chaque instruction :

C++ 
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);>

Par conséquent, le coût total pour effectuer l'opération de somme

Somme=1 + 2 * (n+1) + 2 * n + 1 = 4n + 4 = C1 * n + C2 = O(n)

Par conséquent, la complexité temporelle du code ci-dessus est Sur)

10 ml en onces

Q3. Trouver la somme de tous les éléments d'une matrice

Pour celui-ci, la complexité est une équation polynomiale (équation quadratique pour une matrice carrée)

  • Matrice de taille n*n => Tsum = un.n 2 + b.n + c
  • Puisque Tsum est de l’ordre de n2, donc Complexité temporelle = O(n 2 )
C++ 
#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);>
Sortir 
43>

Complexité temporelle : O(n*m)
Le programme parcourt tous les éléments du tableau 2D à l'aide de deux boucles imbriquées. La boucle externe itère n fois et la boucle interne itère m fois pour chaque itération de la boucle externe. Par conséquent, la complexité temporelle du programme est O(n*m).

Espace auxiliaire : O(n*m)
Le programme utilise une quantité fixe d'espace auxiliaire pour stocker le tableau 2D et quelques variables entières. L'espace requis pour le tableau 2D est de nm nombres entiers. Le programme utilise également une seule variable entière pour stocker la somme des éléments. Par conséquent, la complexité spatiale auxiliaire du programme est O(nm + 1), ce qui se simplifie en O(n*m).

En conclusion, la complexité temporelle du programme est O(nm), et la complexité spatiale auxiliaire est également O(nm).

Ainsi, à partir des exemples ci-dessus, nous pouvons conclure que le temps d'exécution augmente avec le type d'opérations que nous effectuons en utilisant les entrées.

Comment comparer des algorithmes ?

Pour comparer les algorithmes, définissons quelques mesures objectives :

  • Délais d'exécution : Ce n'est pas une bonne mesure car les temps d'exécution sont spécifiques à un ordinateur particulier.
  • Le nombre d'instructions exécutées : Ce n'est pas une bonne mesure, puisque le nombre d'instructions varie selon le langage de programmation ainsi que le style de chaque programmeur.
  • Solution idéale : Supposons que nous exprimions le temps d'exécution d'un algorithme donné en fonction de la taille d'entrée n (c'est-à-dire f(n)) et comparons ces différentes fonctions correspondant aux temps d'exécution. Ce type de comparaison est indépendant du temps machine, du style de programmation, etc.
    Par conséquent, une solution idéale peut être utilisée pour comparer les algorithmes.

Articles Liés:

  • Complexité temporelle et complexité spatiale
  • Analyse des algorithmes | Ensemble 1 (analyse asymptotique)
  • Analyse des algorithmes | Ensemble 2 (pire, moyen et meilleur cas)
  • Analyse des algorithmes | Ensemble 3 (notations asymptotiques)
  • Analyse des algorithmes | Set 4 (Analyse des boucles)
  • Analyse de l'algorithme | Ensemble 5 (Introduction à l'analyse amortie)
  • Divers problèmes de complexité temporelle
  • Questions pratiques sur l'analyse de la complexité temporelle
  • Connaître la complexité de la programmation compétitive