Projete, em pseudocódigo, um algoritmo que receba um vetor A[0..n-1] de inteiros e um inteiro alvo t, e…

Questão

Projete, em pseudocódigo, um algoritmo que receba um vetor A[0..n-1] de inteiros e um inteiro alvo t, e retorne dois índices i<j tais que A[i]+A[j]=t se existirem; prefira solução com tempo O(n) e espaço adicional O(n). Explique correção e complexidade.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

Pseudocódigo: função DoisSoma(A, n, t): mapa := vazio (chave?índice) para i de 0 até n-1 faça complemento := t - A[i] se complemento em mapa então retornar (mapa[complemento], i) fim se mapa[A[i]] := i fim para retornar null // nenhum par encontrado Correção: Ao iterar, para cada A[i] verificamos se já vimos o complemento; se sim, existem índices j<i com A[j]=complemento e A[j]+A[i]=t. Cada par válido é detectado no momento em que o segundo elemento aparece, garantindo i>j. Complexidade: Cada iteração faz busca/inserção esperada O(1) no mapa (hash), totalizando tempo O(n). O espaço adicional é O(n) no mapa no pior caso (armazenando até n chaves).

Explicação

O algoritmo utiliza um mapa para armazenar os elementos já vistos, permitindo verificar rapidamente se o complemento de cada elemento atual já foi encontrado. Isso garante que a soma dos dois elementos seja calculada em tempo linear, já que cada elemento é processado uma única vez. O uso do mapa também assegura que a solução utiliza espaço adicional linear, mantendo a eficiência desejada.

Raio-X da questão

Questões parecidas com resolução

• Um sistema de uma estufa analisa cinco leituras de umidade do solo: 19, 22, 24, 27 e 20. O algoritmo conta as leituras…
• Na montagem de um boletim digital da escola, as seções estão nesta ordem: capa, entrevista, fotos e agenda. A equipe…
• Em um aplicativo da escola, a lista de representantes da turma aparece nesta ordem: Ana, Bia, Caio, Davi e Elisa. Caio…
• Enquanto agentes de manutenção acompanham pedidos de reparo de bicicletas públicas, o painel registra os chamados em uma…
• — O livro de Marina Souza está disponível? — perguntou uma visitante ao balcão da biblioteca municipal. No computador…
• — O kit 47 já foi devolvido? — perguntou a técnica responsável pela campanha itinerante de vacinação. Antes do uso de…

Todas as questões de Programação - Algoritmos clássicos