Melyik algoritmus rendelkezik lineáris O(n) összetettséggel?

Egy O(n) összetettségű algoritmus azt jelenti, hogy a futási idő vagy a felhasznált memória arányosan növekszik a bemeneti adatok n méretével. Ilyen algoritmusokra példák:

1. Maximális vagy minimális elem keresése egy tömbben: Meg kell járni az összes elemet egyszer.

   # Maximális elem keresése
   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áris keresés: Egy adott elem keresése egy nem rendezett listában szekvenciális átvizsgálással.

   // Lineáris keresés
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Elem megtalálva
           }
       }
       return -1; // Elem nem található
   }
   

3. Az elemek gyakoriságának számlálása egy listában: Ehhez egyszer át kell menni a listán, például egy hash-táblával vagy szótárral.

   // Gyakoriság számlálás
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Egyszerű másolat készítése egy tömbről: Új másolat létrehozása az eredeti tömb összes elemének végigjárásával.

5. Az összes elem összegének kiszámítása egy tömbben: Ez egyszeri végigjárást igényel.

Ezekben a példákban az operációk száma közvetlenül arányos az adatok elemeinek számával.