Questão 464164

• Banca: CESGRANRIO
• Órgão: Transpetro
• Ano: 2011
• Provas: CESGRANRIO - 2011 - Transpetro - Analista de Sistemas Júnior
• Disciplina: Algoritmos e Estrutura de Dados
• Assuntos: Algoritmos; Complexidade de Algoritmos

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,

• A. O(1), pois se precisa fazer apenas uma cópia simples de cada um dos elementos originais.
• 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.
• 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.
• D. O(Nlog N), pois se precisa fazer uma busca de cada elemento para depois inseri-lo no vetor de destino.
• 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.

Gabarito: C

Comentários

• A questão descreve um trecho da funcionalidade do algoritmo MergeSort, e o trecho descrito é justamente na hora de juntar os pedaços do vetor que foi dividido e ordenado recursivamente.
  
  Pode-se utilizar, no trecho descrito, a busca binária para determinar a posição onde os elementos do primeiro vetor serão colocados em relação ao segundo vetor. Porém, a questão erra nesse ponto, afirmando o seguinte: 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". O(log N) de fato é a complexidade de uma busca binária, mas o objetivo dessa busca não é determinar qual o próximo elemento a ser copiado, e sim onde o proximo elemento será posicionado.
  
  Por outro lado, esse trecho do algoritmo também pode ser implementado com uma simples busca sequêncial como está descrito na letra C e sua complexidade será justamente O(N).
  
  A busca binária é a melhor escolha para implementar esse "Merge" mas a questão não pergunta isso, ela confunde ao perguntar "A complexidade de tempo de melhor caso desse processo será, então,". Como os dois vetores estão ordenados, uma busca sequêncial será executada sempre no melhor caso, efetuando sempre N comparações, dai pode-se afirmar que a complexidade desse processo é O(N). Se os vetores não estivessem ordenados, a complexidade desse processo seria O(N²).
  
  Resumindo, a alternativa B seria a certa se sua descrição estivesse correta.
• creio que o colega esteja errado,
  
  de qualquer modo, no melhor caso (o caso em tela, visto que ambos vetores já estão ordenados) será necessário realizar 2N cópias para o vetor final, o que resultaria em uma complexidade de melhor caso de O(2N) = O(N)
  
  se eu realizasse uma busca binária, para cada elemento do vetor 1 (que contem N elementos) eu deveria encontrar um vetor menor (ou mesmo não encontrar) no vetor 2 usando busca binária (complexidade O(log N)). Complexidade final: O(N * log N)
  
  não sou um matemático, então corrijam-me se me enganei
• Na época eu caí na casca de banana. Lembrei logo do MergeSort, vi que a letra D tinha a complexidade do MergeSort e marquei logo de cara. Até hoje não compreendi direito por que a resposta não pode ser a letra D, se ela em exatamente a complexidade do MergeSort.
  Desculpem a pergunta idiota, porque vendo a resposta de vocês eu até concordo que irá percorrer no máximo 2N posições. O que não entra na minha cabeça é o fato de a questão estar associada ao algoritmo MergeSort e da resposta não ser a complexidade dele.
• Gente, a questão perguta qual a complexidade no melhor caso. Sabemos que quando os dados (elementos) a serem ordenados já estão praticamente ordenados, os algorítimos de inserção são os mais eficientes. Para n, onde n é o número de valores a serem ordenados e que os valores já estejam ordenados, os algoritimos recomendados são os algorítmos de complexidade quadrática, que no melhor caso tem complexidade linear => O(n). São exemplos de algoritimos de ordenação que teriam complexidade O(n) nesse caso: Insertion Sort, Bubble Sort e Shell Sort. Nesse caso, utilizar algoritimos sofisticados como Quicksort, Mergesort ou Heapsort seria bobagem, pois no melhor caso eles apresentariam somente O(n log n).
  
  Espero ter contribuido! Bons estudos!

• Nelson, obrigada por sua resposta.

  Agora entendi por que a resposta é O(N) e não O(N log N).