Questões Militares de Algoritmos e Estrutura de Dados - Complexidade de Algoritmos

A notação “O” que determina ordem de complexidade e eficiência de um algoritmo pode ser formalizada como se segue:  

                                        T(n) = O (ƒ(n))

                        Se existirem inteiro m e constante c tais que 

                                 T(n) ≤ cƒ(n) para n > m.

Para uma entrada n e um tempo T, melhorias substanciais podem ser obtidas ao utilizarmos diferentes algoritmos. Assinale a alternativa correta com relação ao tempo de execução, para uma mesma entrada (n), porém utilizando algoritmos diferentes. 

Considere as seguintes ordens de complexidade no tempo:  

                       T1(n) = n, T2(n) = nlogn, T3(n) = n² , T4(n) = 2ⁿ 

Segundo Thomas Cormen, cientistas da computação geralmente consideram problemas resolvíveis por algoritmos de tempo polinomial como “tratáveis”, o que quer dizer “fácil de lidar”. Se existir um algoritmo de tempo polinomial para um problema, então se diz que esse problema está na classe P. A respeito dos algoritmos de redução em tempo polinomial, assinale a alternativa correta.

O algoritmo a seguir apresenta uma operação com pilhas.

ocupar (pt);
pt —> info := novo_valor;
pt —> prox := topo;
topo := pt;

Sobre o algoritmo acima é correto afirmar que se refere ao

Analise as informações a seguir

Algoritmo: Rearranja o vetor A[ p..r] em ordem crescente, supondo p≤r QuickSort(A, p, r) 1- se p< r 2- então q < - Particione (A,p, r) 3- QuickSort (A,p, q-1)

4- QuickSort (A, q+ 1, r)
Em uma análise do consumo máximo de tempo do algoritmo QuickSort, considerando a função Particione com desempenho EN, qual é o consumo de tempo no pior caso? Considere n igual ao número máximo de elementos.

Em relação às classes de complexidade de problemas, assinale a opção correta.