Koji algoritam ima linearnu složenost O(n)?

Algoritam sa linearnom složenošću O(n) znači da vreme izvršavanja ili korišćena memorija rastu proporcionalno veličini ulaznih podataka n. Primeri takvih algoritama su:

1. Pretraživanje maksimalnog ili minimalnog elementa u nizu: Potrebno je proći kroz sve elemente niza jednom.

   # Pretraživanje maksimalnog elementa
   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. Linearna pretraga: Pretraživanje određenog elementa u nizu neuređenih podataka putem sekvencijalnog pretraživanja.

   // Linearna pretraga
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element pronađen
           }
       }
       return -1; // Element nije pronađen
   }
   

3. Brojanje učestalosti elemenata u nizu: Za to je potrebno proći kroz niz jednom, koristeći na primer, hash tabelu ili rečnik.

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

4. Jednostavno kopiranje niza: Kreiranje nove kopije niza prolaskom kroz sve elemente originalnog niza.

5. Izračunavanje sume svih elemenata u nizu: Zahteva jedan prolaz kroz sve elemente.

U svim ovim primerima, broj operacija je direktno proporcionalan broju elemenata u obrađivanju podataka.