Care algoritm are o complexitate liniară O(n)?

Un algoritm cu complexitate liniară O(n) înseamnă că timpul de execuție sau memoria utilizată cresc proporțional cu dimensiunea datelor de intrare n. Exemple de astfel de algoritmi sunt:

1. Căutarea elementului maxim sau minim dintr-un array: Este necesar să parcurgi toate elementele array-ului o dată.

   # Căutarea elementului maxim
   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. Căutare liniară: Căutarea unui element specific într-o listă nesortată prin parcurgere secvențială.

   // Căutare liniară
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element găsit
           }
       }
       return -1; // Element negăsit
   }
   

3. Numărarea frecvenței elementelor dintr-o listă: Pentru aceasta, trebuie să parcurgi lista o dată, folosind de exemplu, un tabel hash sau un dicționar.

   // Numărarea frecvenței
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Copiere simplă a unui array: Crearea unei noi copii a array-ului parcurgând toți elementele array-ului original.

5. Calcularea sumei tuturor elementelor dintr-un array: Necesită parcurgerea o singură dată a tuturor elementelor.

În toate aceste exemple, numărul de operații este direct proporțional cu numărul de elemente din datele procesate.