Jaki algorytm ma złożoność liniową O(n)?

Algorytm o złożoności liniowej O(n) oznacza, że czas wykonania lub używana pamięć rosną proporcjonalnie do rozmiaru danych wejściowych n. Przykładami takich algorytmów są:

1. Wyszukiwanie maksymalnego lub minimalnego elementu w tablicy: Należy przejść przez wszystkie elementy tablicy raz.

   # Wyszukiwanie maksymalnego elementu
   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. Przeszukiwanie liniowe: Szukanie określonego elementu na liście nieposortowanej przez przeszukiwanie sekwencyjne.

   // Przeszukiwanie liniowe
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element znaleziony
           }
       }
       return -1; // Element nie znaleziony
   }
   

3. Liczenie częstotliwości elementów na liście: Wymaga przejścia przez listę raz, używając na przykład tablicy haszującej lub słownika.

   // Liczenie częstotliwości
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Proste kopiowanie tablicy: Tworzenie nowej kopii tablicy przez przejście przez wszystkie elementy oryginalnej tablicy.

5. Obliczanie sumy wszystkich elementów w tablicy: Wymaga jednokrotnego przejścia przez wszystkie elementy.

We wszystkich tych przykładach liczba operacji jest bezpośrednio proporcjonalna do liczby elementów w przetwarzanych danych.