Milline algoritm on lineaarse keerukusega O(n)?

Algoritm, mille ajutine keerukus O(n), tähendab, et täitmise aeg või kasutatud mälu kasvab proportsionaalselt sisendandmete suurusega n. Sellised algoritmid on näiteks:

1. Maksimaalse või minimaalse elemendi otsimine massiivis: Tuleb läbi käia kõik massiivi elemendid ühe korra.

   # Maksimaalse elemendi otsimine
   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. Jooneline otsing: Kindla elemendi otsimine korrapäratus nimekirjas, kontrollides järjest iga elementi.

   // Jooneline otsing
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Element leitud
           }
       }
       return -1; // Elementi ei leitud
   }
   

3. Elementide sageduse arvutamine nimekirjas: Selleks tuleb läbi käia nimekiri ühe korra, kasutades näiteks hajemälu või sõnastikku.

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

4. Lihtne massiivi kopeerimine: Uue massiivi loomine, läbides algse massiivi kõik elemendid.

5. Kõigi elementide summa arvutamine massiivis: Nõuab ühekordset läbimist kõigi elementide üle.

Kõigil neil näidetel on operatsioonide arv otseselt proportsionaalne töödeldavate andmete elementide arvuga.