¿Qué algoritmo tiene una complejidad lineal O(n)?

Un algoritmo con complejidad lineal O(n) significa que el tiempo de ejecución o la memoria utilizada crecen proporcionalmente al tamaño de los datos de entrada n. Algunos ejemplos de estos algoritmos son:

1. Buscar el elemento máximo o mínimo en un array: Es necesario recorrer todos los elementos del array una vez.

   # Buscar el elemento máximo
   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. Búsqueda lineal: Buscar un elemento específico en una lista no ordenada mediante búsqueda secuencial.

   // Búsqueda lineal
   public int linearSearch(int[] arr, int target) {
       for (int i = 0; i < arr.length; i++) {
           if (arr[i] == target) {
               return i; // Elemento encontrado
           }
       }
       return -1; // Elemento no encontrado
   }
   

3. Contar la frecuencia de los elementos en una lista: Para esto, hay que recorrer la lista una vez, usando por ejemplo, una tabla hash o un diccionario.

   // Contar la frecuencia de los elementos
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Copiar un array de forma sencilla: Crear una copia nueva del array recorriendo todos los elementos del array original.

5. Calcular la suma de todos los elementos en un array: Requiere recorrer una vez todos los elementos.

En todos estos ejemplos, la cantidad de operaciones es directamente proporcional a la cantidad de elementos en los datos procesados.