Který algoritmus má lineární složitost O(n)?

Algoritmus s lineární složitostí O(n) znamená, že doba běhu nebo používaná paměť roste úměrně velikosti vstupních dat n. Příklady takových algoritmů jsou:

1. Hledání maximálního nebo minimálního prvku v poli: Je třeba projít všechny prvky pole jednou.

   # Hledání maximálního 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ární vyhledávání: Vyhledávání určitého prvku v neuspořádaném seznamu sekvenčním prohledáváním.

   // Lineární vyhledávání
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Prvek nalezen
           }
       }
       return -1; // Prvek nenalezen
   }
   

3. Počítání výskytu prvků v seznamu: K tomu je třeba projít seznam jednou, například pomocí hash tabulky nebo slovníku.

   // Počítání výskytu
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Jednoduché kopírování pole: Vytvoření nové kopie pole průchodem všemi prvky původního pole.

5. Výpočet součtu všech prvků v poli: Vyžaduje jednorázové projití všemi prvky.

Ve všech těchto příkladech je počet operací přímo úměrný počtu prvků zpracovávaných dat.