Кадом алгоритм дорои мураккабиятии хаттӣ O(n)?

Ҳар бир алгоритмнинг O(n) линей мураккаблиги бўлса, бу унинг ишлаш вақти ёки ишлатилган хотираси кириш маълумотларининг n ўлчамига мос равишда ўсиб бораётганини англатади. Бундай алгоритмларга мисоллар:

1. Масивда энг катта ёки энг кичик элементни топиш: Бу учун масивдаги барча элементлардан бир марта ўтиш керак.

   # Энг катта элементни топиш
   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. Чизиқий қидирув: Тартибланмаган рўйхатда муайян бир элементни қидириш учун кетма-кет ўтиш.

   // Чизиқий қидирув
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Элемент топилди
           }
       }
       return -1; // Элемент топилмади
   }
   

3. Рўйхатдаги элементлар учрашувларини ҳисоблаш: Бу учун рўйхатдан бир марта ўтиш керак, масалан, хеш-таблица ёки луғатдан фойдаланиш.

   // Учрашувлар саноати
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Oddiy нусха олиш: Оригинал массивнинг барча элементларини ўтказиб, янги нусха яратиш.

5. Барча элементларнинг жамланишини ҳисоблаш: Бу бир марта барча элементлардан ўтишни талаб қилади.

Бу барча мисолларда амаллар сони ишловчи маълумотлар элементлар сонига тўғридан-тўғри пропорционалдир.