Exercícios de Algoritmos Avançados

Prévia do material em texto

Questão 1 
Assinale a opção correta : 
• A complexidade da multiplicação dos elementos de um vetor com n elementos 
é O(n2). 
• Se tenho 2 algoritmos que resolvem um problema P, ambos com complexidade 
de tempo no pior caso O(n), então sempre posso afirmar que os dois 
algoritmos terão tempos de execução idênticos para entradas do mesmo 
tamanho. 
• Todo trecho com passos elementares, que não dependem do tamanho da 
entrada, possui complexidade constante, ou seja, é O(n). 
• Considere três trechos de um mesmo programa com complexidades O(n), 
O(log2n) e O(n2). A complexidade do programa completo é, no pior caso, 
O(log2n). 
• A complexidade da busca sequencial é O(n) e a da busca binária é O(log2n), o 
que confirma que a busca binária é mais eficiente do que a busca sequencial 
quando a lista está ordenada. 
Questão 2 
Julgue os itens a seguir, acerca de algoritmos para ordenação. 
I. O algoritmo de ordenação por inserção tem complexidade O(n × log n). 
II. Um algoritmo de ordenação é dito estável caso ele não altere a posição relativa 
de elementos de mesmo valor. 
III. No algoritmo quicksort, a escolha do elemento pivô influencia o desempenho 
do algoritmo. 
IV. O bubble-sort e o algoritmo de ordenação por inserção fazem, em média, o 
mesmo número de comparações. 
Estão certos apenas os itens: 
• I e II. 
• I, III e IV. 
• II, III e IV. 
• II e IV. 
• I e III. 
 
Questão 3 
Qual das alternativas abaixo indica um algoritmo de ordenação? 
Ciência da Computação 
• Weber sort. 
• Proxy sort. 
• Bubble sort. 
• Shift sort. 
• Vary sort. 
 
Questão 4 
Analisando a Complexidade do Merge Sort. Consideramos " n "(número de dados a 
serem ordenados) uma potência de 2 e a seguinte equação de recorrência, T(n) é o 
tempo para uma entrada de tamanho n. 
T(1)=1(caso base) 
T(n)=2T(n/2)+3(n-1) 
Temos 2 chamadas recursivas como n/2 e um total de 3(n-1) intercalações por 
aproximação vamos considerar n intercalações. Sendo assim faz sentido escrever 
T(n) = 2T(n/2) + n 
Uma vez que podemos substituir n/2 na equação principal. 
2T(n/2) = 2(2T(n/4) + n/2) 
2T(n/2) = 4T(n/4) + n 
Logo: 
T(n) = 2T(n/2) + n 
T(n) = 4T(n/4) + n + n 
T(n) = 4T(n/4) + 2n 
Assim se continuarmos a análise da equação, chegaremos a conclusão que a 
complexidade de pior caso para o MergeSort é: 
• O(log n). 
• O(n). 
• O(n lg n) , onde lg é log na base 2. 
• O(1). 
• O(n^2) onde n^2 é n elevado a 2. 
Questão 5 
Ao analisarmos a complexidade de um algoritmo, podemos relacioná-lo a um tipo de 
caso a ser estudado. Quando resolvemos analisar o algoritmo pela ótica mais 
pessimista de sua execução, escolhemos a: 
• Definição Θ (Theta). 
• Definição O. 
• Notação Ω (Ômega). 
• Notação Θ (Theta). 
• Notação O.