Complexidade de Algoritmos
Uma fábrica de software foi contratada para desenvolver um produto de análise de riscos. Em determinada funcionalidade desse software, é necessário realizar a ordenação de um conjunto formado por muitos números inteiros. Que algoritmo de ordenação oferece melhor complexidade de tempo (Big O notation) no pior caso?
A respeito dos métodos de ordenação, pesquisa e hashing, julgue o seguinte item.

A eficácia do método de ordenação rápida (quicksort) depende da escolha do pivô mais adequado ao conjunto de dados que se deseja ordenar. A situação ótima ocorre quando o pivô escolhido é igual ao valor máximo ou ao valor mínimo do conjunto de dados.
Os dados que são tratados por um sistema de computação podem possuir diferentes tipos de organização natural. Para lidar com essa diversidade de organizações naturais, diferentes tipos de estruturas de dados podem ser utilizados.

Acerca dos principais tipos de estruturas de dados, julgue o item subseqüente.

Operações de busca em uma árvore binária envolvem, no mínimo, N2N \over 2 operações de comparação, em que NN é o número de elementos contidos na árvore binária.
Na pior hipótese, o número de comparações necessárias para pesquisar um elemento em um array de 2048 elementos pelo método pesquisa binária será
Existem diferentes métodos de ordenação na memória, cada um com características próprias, que permitem melhor adaptação a uma determinada quantidade ou tipo de dados. Considere os métodos de classificação abaixo:

I - Classificação por troca ou método da bolha - o vetor é percorrido seqüencialmente várias vezes. Cada passagem consiste em comparar cada elemento com seu sucessor (x[i] com x[i+1]) e trocar os dois elementos, se eles não estiverem na ordem correta.

II- Classificação por troca de partição ou quicksort - o vetor é particionado em dois subconjuntos, um à direita e outro à esquerda, de tal forma que todo elemento do subconjunto à esquerda é menor que qualquer elemento do subconjunto à direita. Cada um dos subconjuntos é reparticionado sucessivas vezes, segundo o mesmo critério.

Acerca dos métodos de classificação considerando n elementos, julgue o seguinte item.

O quicksort tem melhor desempenho para vetores classificados, apresentando em média nlogn comparações.