Кай алгоритмдин убакыттык кыйынчылыгы 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. Жөнөкөй көчүрмө алуу: Оргинал массивдин бардык элементтерин өтүп, жаңы көчүрмө түзүү.

5. Бардык элементтердин суммасын эсептөө: Бул бир жолу өтүүнү талап кылат.

Бул бардык мисолдордо операциялардын саны иштетилүүчү маалыматтардын элементтеринин санына түз пропорционал.