Welcher Algorithmus hat eine lineare Komplexität O(n)?

Ein Algorithmus mit linearer Komplexität O(n) bedeutet, dass die Ausführungszeit oder der verwendete Speicher proportional zur Größe der Eingabedaten n wächst. Beispiele für solche Algorithmen sind:

1. Suche nach dem maximalen oder minimalen Element in einem Array: Es ist notwendig, alle Elemente des Arrays einmal zu durchlaufen.

   # Suche nach dem maximalen 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. Lineare Suche: Suche nach einem bestimmten Element in einer ungeordneten Liste durch sequentielle Durchsuchung.

   // Lineare Suche
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element gefunden
           }
       }
       return -1; // Element nicht gefunden
   }
   

3. Zählen der Häufigkeit von Elementen in einer Liste: Dafür muss die Liste einmal durchlaufen werden, z.B. mit einer Hashtabelle oder einem Wörterbuch.

   // Zählen der Häufigkeit von Elementen
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Einfache Kopie eines Arrays: Erstellen einer neuen Kopie des Arrays durch Durchlaufen aller Elemente des Originalarrays.

5. Berechnung der Summe aller Elemente im Array: Erfordert einmaliges Durchlaufen aller Elemente.

In all diesen Beispielen ist die Anzahl der Operationen direkt proportional zur Anzahl der Elemente in den verarbeiteten Daten.