Кой алгоритъм има линейна сложност 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. Изчисляване на сумата на всички елементи в масива: Изисква еднократно преминаване през всички елементи.

Във всички тези примери броят на операциите е директно пропорционален на броя на елементите в обработваните данни.