Questão nº 47

Questão de Tecnologia da Informação · FGV TJ-SE Servidor 2023 (nº 47)

FGV2023Analista Judiciário - Análise de SistemasTecnologia da Informação

Considere o código JavaScript nas duas questões a seguir.

function numeros(L, N) {
x1 = 0;

x2 = L.length-1;

while (x1 < x2) {

    if (L[x2] >= N) {

        x2 = x2 - 1;

    } else if (L[x1] + L[x2] != N) {

        x1 = x1 + 1;

    } else if (L[x1] + L[x2] == N) {

        return true;

    } else {

        return false;

    }

}

return false;
}

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); (alternativa correta)
EO(N²).

Resposta comentada

Gabarito Alternativa D

A complexidade de algoritmos (representada pela notação Big O) descreve como o tempo de execução ou o espaço de memória de um algoritmo cresce em relação ao tamanho da entrada. Ela nos ajuda a entender a eficiência de um algoritmo, focando no pior caso de desempenho.

(A) Incorreta: O(1) significa tempo constante, ou seja, o tempo de execução não muda com o tamanho da entrada, o que não é o caso aqui, pois o algoritmo itera sobre o array.
(B) Incorreta: O(log N) significa tempo logarítmico, geralmente associado a algoritmos que dividem o problema pela metade a cada passo (como busca binária). Embora os ponteiros se movam, eles não reduzem o espaço de busca logaritmicamente em cada iteração.
(C) Incorreta: O(N log N) é comum em algoritmos de ordenação eficientes ou em problemas que envolvem ordenação seguida de processamento, o que não se aplica diretamente a este algoritmo de dois ponteiros.
(D) Correta: O(N) significa tempo linear. Neste algoritmo, os ponteiros x1 e x2 começam nas extremidades do array L e se movem em direção ao centro. Em cada iteração do loop while, ou x1 é incrementado, ou x2 é decrementado. Isso significa que a distância entre x1 e x2 diminui a cada passo. No pior caso, os ponteiros se encontrarão ou se cruzarão após percorrerem o array uma única vez. Portanto, o número total de operações é diretamente proporcional ao número de elementos (N) no array L.
(E) Incorreta: O(N²) significa tempo quadrático, que geralmente ocorre com loops aninhados onde o loop interno executa N vezes para cada iteração do loop externo (por exemplo, comparar cada elemento com todos os outros). Este algoritmo utiliza apenas um único loop while com dois ponteiros, não loops aninhados.

Fonte: FGV TJ-SE Servidor 2023 Analista Judiciário - Análise de Sistemas (Caderno Tipo 1). Reproduzida para fins de estudo.

Questão de Tecnologia da Informação · FGV TJ-SE Servidor 2023 (nº 47)

Resposta comentada

Continue estudando