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

• Projete um algoritmo em pseudocódigo que, dado um vetor V de n inteiros e um inteiro k, determine se existem índices i <…
• Escreva um algoritmo em pseudocódigo que, dado um vetor ordenado de dados inteiros e uma variável alvo, use busca…
• Projete um algoritmo em pseudocódigo que, dado um vetor de números inteiros com tamanho par, percorra o vetor em pares…
• Escreva um pseudocódigo que, dada uma lista A de n inteiros, percorra pares ordenados (i,j) com i<j usando loops…
• Projete um algoritmo em pseudocódigo que, dado um vetor A[1..n] de inteiros, encontre o comprimento do maior subvetor…
• Projete em pseudocódigo um algoritmo que remova, in-place, todas as ocorrências de um valor v em um vetor A de…

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