Questões Militares de Algoritmos e Estrutura de Dados - Complexidade de Algoritmos
Foram encontradas 11 questões
Coloque F (falso) ou V (verdadeiro) nas funções abaixo, considerando a notação de complexidade O, e assinale a seguir a opção correta.
( ) f - 9 + log n = 0(n)
( ) f= 255 = 0(1)
( ) f = 37 + 215n = 0(2n)
( ) f=25 + 218+n = 0(2n)
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) = 2n
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
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.
Analise as informações abaixo.
Algoritmo: Rearranja o vetor A [ p..r] em ordem crescente, supondo p≤r; Merge-Sort (A, p, r) 1 - se p ≤ r
2 - então
3- Merge-Sort (A, p, q)
4- Merge-Sort (A, q+ 1, r)
5- Intercala (A, p, q, r)
Em uma análise do algoritmo Merge-Sort, considerando a função Intercala com desempenho O (n) , qual é o consumo de tempo no pior caso? Considere n igual ao número máximo de elementos.
Conheça nossos planos