João precisa codificar uma função f(A), onde A é um array unidimensional de números inteiros, que deve retornar o maior valor armazenado em A. A complexidade de um algoritmo eficiente para a função f, para um array com n (n ≥ 1) elementos, deveria ser:
- A)O(1)
Errada, porque em tempo constante voce nao consegue garantir o maior valor de um array nao ordenado sem analisar os elementos.
- B)O(log n)
Errada, pois O(log n) aparece em algoritmos que reduzem o problema por divisao sucessiva, o que nao ocorre aqui.
- C)O(n)
Certa, porque encontrar o maior em um array exige uma passada linear pelos elementos, com custo proporcional a n.
- D)O(n log n)
Errada, pois O(n log n) e tipico de ordenacao ou algoritmos divide and conquer mais pesados, nao de uma simples busca do maximo.
- E)O(n²)
Errada, porque O(n²) seria um custo muito maior, com comparacoes repetidas desnecessarias para esse problema.
Gabarito: C
Para descobrir o maior valor em um array de inteiros, voce precisa olhar os elementos e comparar um por um. Isso porque, em uma lista sem informacao extra sobre a ordenacao, nao existe atalho magico: o maior pode estar em qualquer posicao, inclusive no fim, e voce so confirma isso verificando os valores. A ideia do algoritmo eficiente e simples: assumir que o primeiro elemento e o maior ate prova em contrario e, em seguida, percorrer o restante do array atualizando esse valor quando encontrar um numero maior. Esse tipo de varredura completa faz uma passada pelos n elementos, entao o custo cresce de forma linear. Por isso, a complexidade esperada e O(n). Em notacao Big O, esse eh o comportamento da funcao quando o numero de operacoes aumenta proporcionalmente ao tamanho da entrada. Nao da para ser O(1), porque uma unica leitura nao garante achar o maior; nem O(log n), O(n log n) ou O(n²), porque nao ha necessidade de dividir, ordenar ou comparar repetidamente os elementos. Em resumo: para achar o maior de um array nao ordenado, voce precisa inspecionar praticamente todos os itens. E quando a tarefa e simplesmente varrer a estrutura uma vez, a resposta classica de concurso e linearidade pura e honesta: O(n).