Какой алгоритм имеет линейную сложность 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. Вычисление суммы всех элементов в массиве: Требует однократного прохода по всем элементам.

Во всех этих примерах количество операций прямо пропорционально количеству элементов в обрабатываемых данных.