Questão de Programação — Linguagens de programação — FGV 2023
Programação›Linguagens de programação
Código
fg072588
Banca
FGV
Órgão
TJ-SE
Ano
2023
Nível
Superior
Cargo
Analista Judiciário - Especialidade - Análise de Sistemas
Considere o código JavaScript na questão a seguir.
O parâmetro L deve ter como valor um array com números
inteiros, maiores que zero, dispostos em ordem crescente.
De acordo com o número de elementos no array fornecido como parâmetro para função numeros, apresentada anteriormente, a complexidade do algoritmo utilizado é:
AO(1);
BO(log N);
CO(N log N);
DO(N);
EO(N² ).
Revelar gabarito e comentário▾
GabaritoD — O(N);
Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.
Complexidade de Algoritmos: Análise Assintótica
Gabarito: letra D. A complexidade do algoritmo é O(N), pois o tempo de execução cresce linearmente com o número de elementos do array de entrada. Isso significa que, se o array tiver N elementos, o algoritmo realizará um número de operações proporcional a N, como em um único loop que percorre todos os elementos.
A análise de complexidade de algoritmos é uma ferramenta fundamental para avaliar a eficiência de um código, especialmente quando lidamos com grandes volumes de dados. Ela descreve como o tempo de execução (ou uso de memória) de um algoritmo cresce à medida que o tamanho da entrada aumenta. A notação Big O é a mais comum para expressar essa complexidade, focando no termo dominante do crescimento e ignorando constantes e termos de menor ordem.
Para entender a complexidade, é preciso identificar a operação mais frequente no algoritmo e contar quantas vezes ela é executada em função do tamanho da entrada (N). Por exemplo, um algoritmo que percorre um array uma única vez, realizando uma operação constante em cada elemento, tem complexidade O(N). Já um algoritmo que, para cada elemento, percorre novamente todo o array, tem complexidade O(N²).
A questão pede para analisar a função numeros, que recebe um array L de números inteiros positivos em ordem crescente. A complexidade depende diretamente de como o algoritmo processa esse array. Se ele itera sobre todos os elementos uma única vez, a complexidade é linear, O(N). Se ele usa uma busca binária, a complexidade seria O(log N), mas isso só se aplica a buscas em estruturas ordenadas, não a uma varredura completa.
A pegadinha da banca está em confundir a complexidade de um algoritmo que percorre o array inteiro com a de algoritmos de busca ou ordenação. A presença de um array ordenado pode sugerir uma busca binária (O(log N)), mas se o algoritmo precisa examinar cada elemento, a complexidade é O(N). É crucial analisar o código para verificar se há loops aninhados (O(N²)) ou se a operação é constante (O(1)).
Para resolver a questão, é essencial identificar a estrutura de repetição dominante no código da função numeros. Se houver um único loop que percorre o array do início ao fim, a complexidade é O(N). Se houver dois loops aninhados, cada um percorrendo o array, a complexidade é O(N²). A resposta correta é a que corresponde à estrutura do algoritmo apresentado.
Complexidade de algoritmos: O(1) (Tempo constante, Acesso por índice); O(log N) (Divide o problema pela metade, Busca binária); O(N) (Cresce linearmente, Loop simples no array); O(N log N) (Ordenação eficiente, Merge Sort, Quick Sort); O(N²) (Cresce quadraticamente, Dois loops aninhados)
Alternativa A — ❌ Incorreta
A complexidade O(1) indica que o tempo de execução é constante, independente do tamanho da entrada. Isso só ocorre em operações como acessar um elemento específico de um array por índice ou realizar uma operação aritmética simples. Como o algoritmo processa o array, ele não pode ter complexidade constante, a menos que apenas examine um número fixo de elementos, o que não é o caso de uma varredura completa.
Alternativa B — ❌ Incorreta
A complexidade O(log N) é típica de algoritmos que dividem o problema pela metade a cada passo, como a busca binária. Embora o array esteja ordenado, a busca binária só é eficiente para encontrar um elemento específico, não para processar todos os elementos. Se o algoritmo percorre o array inteiro, a complexidade é linear, não logarítmica.
Alternativa C — ❌ Incorreta
A complexidade O(N log N) é comum em algoritmos de ordenação eficientes, como Merge Sort e Quick Sort. Ela indica que o algoritmo realiza uma operação logarítmica para cada elemento. Se o algoritmo apenas percorre o array uma vez, sem realizar operações de divisão ou ordenação, a complexidade não é O(N log N).
Alternativa D — ✅ Correta ⟵ GABARITO
A complexidade O(N) indica que o tempo de execução cresce linearmente com o tamanho da entrada. Isso ocorre quando o algoritmo percorre o array uma única vez, realizando uma operação de custo constante em cada elemento. É a complexidade típica de um loop simples que itera sobre todos os elementos de um array, como for (let i = 0; i < L.length; i++). Como o algoritmo processa cada elemento do array, a complexidade é proporcional a N.
Alternativa E — ❌ Incorreta
A complexidade O(N²) indica que o tempo de execução cresce quadraticamente com o tamanho da entrada. Isso ocorre quando há dois loops aninhados, cada um percorrendo o array, resultando em N × N operações. Se o algoritmo não possui loops aninhados, a complexidade não é quadrática.
PEGA ESSA DICA!
Para identificar a complexidade de um algoritmo, procure os loops. Um loop simples percorrendo N elementos indica O(N). Dois loops aninhados indicam O(N²). Um loop que divide o problema pela metade a cada iteração indica O(log N). A ordenação eficiente geralmente tem O(N log N).
