Questão 870196

Tecnologia da Informação · 2011

Questão

ID 870196

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2011 Banca: Fundação CESGRANRIO Órgão: Petrobras Transporte S/A

Dois vetores ordenados, contendo, cada um deles, N números inteiros, precisam ser unidos em outro vetor maior, que conterá os 2N números, que também serão armazenados de forma ordenada. A complexidade de tempo de melhor caso desse processo será, então,

Alternativa A:
O(1), pois se precisa fazer apenas uma cópia simples de cada um dos elementos originais.
Alternativa B:
O(log N), pois se usa a busca binária para determinar qual será o próximo elemento copiado para o vetor de destino.
Alternativa C:
O(N), pois se precisa fazer uma cópia de cada um dos elementos originais, o que implica uma varredura completa de cada vetor de origem.
Alternativa D:
O(Nlog N), pois se precisa fazer uma busca de cada elemento para depois inseri-lo no vetor de destino.
Alternativa E:
O(N²), pois, como há dois vetores, precisa-se fazer dois laços de forma aninhada (um dentro do outro), gerando uma multiplicação das quantidades de elementos.

Estatísticas Cadernos

Questão 870196

Continue estudando na plataforma