Welke algoritme heeft een lineaire complexiteit O(n)?

Een algoritme met lineaire complexiteit O(n) betekent dat de uitvoeringstijd of het gebruikte geheugen evenredig groeit met de grootte van de invoergegevens n. Voorbeelden van dergelijke algoritmen zijn:

1. Zoeken naar het maximale of minimale element in een array: Het is nodig om alle elementen van de array één keer te doorlopen.

   # Zoek het maximale element
   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. Lineair zoeken: Het zoeken naar een bepaald element in een niet-gesorteerde lijst door sequentiële doorloop.

   // Lineair zoeken
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element gevonden
           }
       }
       return -1; // Element niet gevonden
   }
   

3. Telling van de frequentie van elementen in een lijst: Hiervoor moet de lijst één keer worden doorlopen, bijvoorbeeld met een hash-tabel of woordenboek.

   // Frequentietelling
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Eenvoudige kopie van een array: Het maken van een nieuwe kopie van de array door alle elementen van de originele array te doorlopen.

5. Berekenen van de som van alle elementen in een array: Vereist één keer doorlopen van alle elementen.

In al deze voorbeelden is het aantal bewerkingen recht evenredig met het aantal elementen in de verwerkte gegevens.