Questão 1

Analise a questão da influência da ordem inicial das chaves em cada um dos seguintes métodos: Shellsort, Bubblesort e Heapsort para classificar em ordem crescente valores. Preencha então as lacunas com “V”, quando a sentença é verdadeira, ou com “F” quando for falsa.

(F) Quando inicialmente as n chaves estão em ordem crescente o tempo de execução do Bubblesort é n comparações. (n-1)

(V) A ordem inicial das chaves não influencia o tempo de execução do Heapsort.

(V) A ordem inicial das chaves influencia o tempo de execução do Shellsort.

(V) Somente quando inicialmente as n chaves estão em ordem decrescente o tempo de execução do Quicksort original (escolha sistemática do extremo como pivô) é o pior caso, ou seja O(n2).

Questão 2 :

Um algoritmo polinomial é sempre melhor que o um algoritmo exponencial?
Nem sempre, pois para números de n pequenos o exponecial é melhor.

Questão 3 :

Preencha as linhas tracejadas abaixo.

Para dobrar o tempo de execução de um algoritmo de complexidade O(log n) temos que considerar n² elementos de entrada.

Um algoritmo de complexidade O(1) é dito de complexidade constante.

Sempre que o n dobra e o tempo de execução também dobra o algoritmo é dito de complexidade linear.

Quando representamos a complexidade de um algoritmo como O(2 log n) e Ômega (log n) podemos representar esta mesma complexidade como teta (log n)

Questão 4:

Discuta o problema da classificação de grandes volumes de dados (grandes volumes de dados não cabem em memória principal).

O ideal num caso desses é usar algum algoritmo que divida o arquivo em arquivos menores e organize-os individualmente como por exemplo o merge sort, em que poderiamos dividir o arquivo em pequenos arquivos temporários que caibam na memória e depois uní-los num arquivo maior e organizado.