Quale algoritmo ha una complessità lineare O(n)?

Un algoritmo con complessità lineare O(n) significa che il tempo di esecuzione o la memoria utilizzata crescono proporzionalmente alla dimensione dei dati di input n. Alcuni esempi di tali algoritmi sono:

1. Ricerca dell'elemento massimo o minimo in un array: È necessario attraversare tutti gli elementi dell'array una volta.

   # Ricerca dell'elemento massimo
   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. Ricerca lineare: Ricerca di un elemento specifico in una lista non ordinata tramite scansione sequenziale.

   // Ricerca lineare
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Elemento trovato
           }
       }
       return -1; // Elemento non trovato
   }
   

3. Contare la frequenza degli elementi in una lista: Per questo bisogna attraversare la lista una volta, usando ad esempio una tabella hash o un dizionario.

   // Contare la frequenza
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Copia semplice di un array: Creare una nuova copia dell'array attraversando tutti gli elementi dell'array originale.

5. Calcolare la somma di tutti gli elementi in un array: Richiede di attraversare tutti gli elementi una volta.

In tutti questi esempi, il numero di operazioni è direttamente proporzionale al numero di elementi nei dati elaborati.