Analise, no código JavaScript exibido a seguir, a função f que recebe um array como parâmetro. É dado que a função Math.trunc retorna a parte inteira de um número. javascript function f(x) { i = 0; for (i=0; i < Math.trunc(x.length/2); i++) { a = x[i]; x[i] = x[x.length -i -1]; x[x.length -i -1] = a; } return x; } A complexidade do algoritmo é da ordem: ---

Questão nº 52

Questão de Tecnologia da Informação · FGV TJ-AP 2024 (nº 52)

FGV2024Analista Judiciário - TI - Banco de DadosTecnologia da Informação

Analise, no código JavaScript exibido a seguir, a função f que recebe um array como parâmetro. É dado que a função Math.trunc retorna a parte inteira de um número.

function f(x) {
    i = 0;
    for (i=0; i < Math.trunc(x.length/2); i++) {
      a = x[i];
      x[i] = x[x.length -i -1];
      x[x.length -i -1] = a;
    }
    return x;
}

A complexidade do algoritmo é da ordem:

ALog (N)
BN Log(N)
CN/2 (alternativa correta)
DN
EN²

Resposta comentada

Gabarito Alternativa C

A complexidade de tempo de um algoritmo mede quantos passos ele executa em relação ao tamanho da entrada (N). Geralmente, usamos a notação Big O para descrever o comportamento assintótico (como o número de passos cresce para entradas muito grandes), ignorando constantes e termos de menor ordem.

(A) Incorreta: Log (N) indica que o número de operações cresce logaritmicamente com o tamanho da entrada, o que não ocorre aqui.
(B) Incorreta: N Log(N) é a complexidade de algoritmos de ordenação eficientes, não aplicável a esta função.
(C) Correta: A função executa um laço for que itera Math.trunc(x.length/2) vezes. Se N é o tamanho do array x, o laço executa N/2 vezes (arredondado para baixo). Cada iteração realiza um número constante de operações. Portanto, o número de operações é diretamente proporcional a N/2. A banca, ao oferecer N/2 e marcá-lo como correto, está pedindo a contagem precisa das iterações do laço, e não a notação assintótica Big O.
(D) Incorreta: N seria a complexidade na notação Big O (O(N)), pois O(N/2) é assintoticamente equivalente a O(N). No entanto, a armadilha da banca é justamente levar o aluno a pensar em Big O e escolher N, quando a questão permite uma resposta mais precisa (N/2) sobre o número de iterações do laço, e esta é a alternativa correta segundo o gabarito.
(E) Incorreta: N² indica que o número de operações cresce quadraticamente com o tamanho da entrada, geralmente por laços aninhados, o que não é o caso desta função.

Fonte: FGV TJ-AP 2024 Analista Judiciário - TI - Banco de Dados (Caderno Tipo 1). Reproduzida para fins de estudo.

Questão de Tecnologia da Informação · FGV TJ-AP 2024 (nº 52)

Resposta comentada

Continue estudando