Kura algoritma ir lineāra sarežģītība O(n)?

Algoritms ar lineāru sarežģītību O(n) nozīmē, ka izpildes laiks vai izmantotā atmiņa pieaug proporcionāli ievades datu lielumam n. Šādi algoritmi ir piemēri:

1. Maksimālā vai minimālā elementa meklēšana masīvā: Ir nepieciešams vienreiz pārskatīt visus masīva elementus.

   # Maksimālā elementa meklēšana
   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. Līnija meklēšana: Noteikta elementa meklēšana nesakārtotā sarakstā, secīgi pārbaudot katru elementu.

   // Līnija meklēšana
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Elements atrasts
           }
       }
       return -1; // Elements nav atrasts
   }
   

3. Elementu biežuma skaitīšana sarakstā: Tam nepieciešams vienreiz pārskatīt sarakstu, izmantojot piemēram, haštabulu vai vārdnīcu.

   // Biežuma skaitīšana
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Vienkārša masīva kopēšana: Izveido jaunu masīva kopiju, pārejot pa visiem sākotnējā masīva elementiem.

5. Visu elementu summas aprēķināšana masīvā: Prasa vienu pāreju pa visiem elementiem.

Visos šajos piemēros operāciju skaits ir tieši proporcionāls apstrādājamo datu elementu skaitam.