Qual algoritmo tem uma complexidade linear O(n)?

Um algoritmo com complexidade linear O(n) significa que o tempo de execução ou a memória utilizada crescem proporcionalmente ao tamanho dos dados de entrada n. Alguns exemplos desses algoritmos são:

1. Procura do elemento máximo ou mínimo num array: É necessário percorrer todos os elementos do array uma vez.

   # Procura do 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. Procura linear: Procura de um elemento específico numa lista não ordenada por busca sequencial.

   // Procura linear
   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 não encontrado
   }
   

3. Contagem da frequência dos elementos numa lista: Para isso, é preciso percorrer a lista uma vez, usando por exemplo, uma tabela hash ou um dicionário.

   // Contagem da frequência dos elementos
   function countFrequency(arr) {
     const frequency = {};
     for (const element of arr) {
       frequency[element] = (frequency[element] || 0) + 1;
     }
     return frequency;
   }
   

4. Cópia simples de um array: Criação de uma nova cópia do array percorrendo todos os elementos do array original.

5. Cálculo da soma de todos os elementos num array: Requer percorrer todos os elementos uma vez.

Em todos esses exemplos, a quantidade de operações é diretamente proporcional à quantidade de elementos nos dados processados.