Quel algorithme a une complexité linéaire O(n) ?

Un algorithme avec une complexité linéaire O(n) signifie que le temps d'exécution ou la mémoire utilisée croît proportionnellement à la taille des données d'entrée n. Voici quelques exemples de tels algorithmes :

1. Recherche du maximum ou du minimum dans un tableau : Il faut parcourir tous les éléments du tableau une fois.

   # Recherche du maximum
   def find_max(arr):
       if not arr:
           return None
       max_val = arr[0]
       for element in arr:
           if element > max_val:
               max_val = element
       return max_val
   

2. Recherche linéaire : Recherche d'un élément spécifique dans une liste non triée par parcours séquentiel.

   // Recherche linéaire
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Élément trouvé
           }
       }
       return -1; // Élément non trouvé
   }
   

3. Comptage de la fréquence des éléments dans une liste : Pour cela, il faut parcourir la liste une fois, en utilisant par exemple une table de hachage ou un dictionnaire.

   // Comptage de la fréquence des éléments
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Copie simple d'un tableau : Création d'une nouvelle copie du tableau en parcourant tous les éléments du tableau original.

5. Calcul de la somme de tous les éléments dans un tableau : Nécessite de parcourir tous les éléments une fois.

Dans tous ces exemples, le nombre d'opérations est directement proportionnel au nombre d'éléments dans les données traitées.