Kuris algoritmas turi linijinę sudėtingumą O(n)?

Algoritmas, turintis linijinį sudėtingumą O(n), reiškia, kad vykdymo laikas arba naudojama atmintis auga proporcingai įvesties duomenų dydžiui n. Tokie algoritmai yra pavyzdžiui:

1. Didžiausio arba mažiausio elemento paieška masyve: Reikia vieną kartą pereiti per visus masyvo elementus.

   # Didžiausio elemento paieška
   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. Linjinis paieška: Nustatyto elemento paieška nesutvarkytame sąraše nuosekliai tikrinant kiekvieną elementą.

   // Linijinė paieška
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Elementas rastas
           }
       }
       return -1; // Elementas nerastas
   }
   

3. Elemento dažnio skaičiavimas sąraše: Tam reikia vieną kartą pereiti per sąrašą, naudojant pavyzdžiui, žemėlapį arba žodyną.

   // Dažnio skaičiavimas
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Paprastas masyvo kopijavimas: Sukuriama nauja masyvo kopija pereinant per visus pradinio masyvo elementus.

5. Visų elementų sumos skaičiavimas masyve: Reikalauja vieno praeinimo per visus elementus.

Visais šiais pavyzdžiais operacijų skaičius tiesiogiai proporcingas apdorojamų duomenų elementų skaičiui.