Aký algoritmus má lineárnu zložitosť O(n)?

Algoritmus s lineárnou zložitosťou O(n) znamená, že doba vykonávania alebo použitá pamäť rastie úmerne veľkosti vstupných údajov n. Príklady takýchto algoritmov sú:

1. Hľadanie maximálneho alebo minimálneho prvku v poli: Je potrebné prejsť všetky prvky poľu raz.

   # Hľadanie maximálneho prvku
   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. Lineárne vyhľadávanie: Vyhľadávanie určitého prvku v neusporiadanom zozname sekvenčným prehľadávaním.

   // Lineárne vyhľadávanie
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Prvok nájdený
           }
       }
       return -1; // Prvok nenájdený
   }
   

3. Počítanie frekvencie prvkov v zozname: Na to je potrebné prejsť zoznam raz, napríklad pomocou hash tabuľky alebo slovníka.

   // Počítanie frekvencie
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Jednoduché kopírovanie poľa: Vytvorenie novej kópie poľa prechodom všetkých prvkov pôvodného poľa.

5. Výpočet súčtu všetkých prvkov v poli: Vyžaduje jeden prechod všetkých prvkov.

Vo všetkých týchto príkladoch je počet operácií priamo úmerný počtu prvkov v spracovávaných dátach.