Lista de Exercícios - Análise de Algoritmos

Prévia do material em texto

Alcides Tiago Medeiros Dantas – 20211014040078 
TECNOLOGIA EM ANÁLISE E DESENVOLVIMENTO DE SISTEMAS – IFRN 
NATAL – RN 
2021 
Lista de Exercícios – Análise de Algoritmos 
ALGORITMOS 
 
 
1 
1. (10 pontos) Considere as equações de tempo de execução dos algoritmos A e B a 
seguir 
• T (A) = 100n + 500 
• T (B) = 2n2 + 10 
onde n é o tamanho da entrada. 
Escreva uma análise comparativa sobre o desempenho de A e B em função do 
tamanho da entrada. Para realizar a análise forneça as informações a seguir. 
(a) Determine para quais faixas de valores A é melhor do que B e B é melhor 
do que A, considerando eficiência temporal. 
R: O algoritmo A passa a ser mais vantajoso que o Algoritmo B quando tem-
se o tamanho da entrada por volta de 55 em diante, que é quando se dispõe 
de uma discrepância cada vez mais alarmante entre o Algoritmo A e o 
Algoritmo B, sendo o Algoritmo A mais eficiente para essa situação. Dessa 
forma, por outro lado, para um tamanho de entrada menor que 55, o 
algoritmo B supera em eficiência o algoritmo A. 
(b) Desenhe o gráfico das funções dos algoritmos A e B. 
 
 
Algoritmo A 
Algoritmo B 
2 
2. (10 pontos) Escreva um algoritmo que encontre o menor elemento de array de n 
elementos. Encontre a equação do tempo de execução do algoritmo. 
 
#include <iostream> 
 
using namespace std; 
 
int main(){ 
 
 int tamanho; 
 cin >> tamanho; 
 int array[tamanho]; 
 int menor = 0; 
 
 // Preenchendo array 
 for (int i = 0; i < tamanho; i++){ 
 cin >> array[i]; 
 } 
 
 // Encontrando menor elemento do array (Apenas o que é considerado no enunciado a 
fim de contabilizar para a equação) 
 menor = array[0]; // 2 
 
 for (int i = 0; i < tamanho; i++){ // 2n 
 if (array[i] < menor){ // 2*(n - 1) 
 menor = array[i]; // 2*(n - 1) 
 } 
 } //Incremento = 2*(n - 1) 
 
 cout << "O menor elemento do array é: " << menor << "\n"; //1 
} 
 
A equação final do tempo de execução do algoritmo é aproximadamente: 8n – 3 
3 
3. (10 pontos) Escreva um algoritmo que determine se um valor V encontra-se em um 
array de n elementos. Escreva a equação de tempo de execução do seu algoritmo. 
 
#include <iostream> 
 
using namespace std; 
 
int main(){ 
 
 int tamanho; 
 cin >> tamanho; 
 int array[tamanho]; 
 
 // Preenchendo array 
 for (int i = 0; i < tamanho; i++){ 
 cin >> array[i]; 
 } 
 
 // Percorrendo o array (apenas o que é considerado no enunciado a fim de contabilizar 
para a equação) 
 bool existe = false; // 1 
 for (int i = 0; i < tamanho; i++){ // 2n 
 if (array[i] == 9){ // 2*(n - 1) 
 existe = true; // 1 
 break; // 1 
 } 
 
 } //Incremento = 2*(n - 1) 
 
 cout << existe << "\n"; // 1 
 
} 
A equação final do tempo de execução do algoritmo é aproximadamente: 6n 
 
4. (10 pontos) Sejam 4 diferentes algoritmos com as equações de tempo de execução a 
seguir: 
(a) 
2𝑛
8
 + 2n 
(b) 10n + 50 
(c) 10 + 2n2 + n 
(d) 100 + 20log2n 
 
Preencha a tabela a seguir e classifique os algoritmos do melhor (mais rápido) para 
o pior. 
Entrada 2 4 6 8 10 12 14 16 18 20 
4 
 
Faça um gráfico com as 4 equações para facilitar a visualização. 
Classificação dos algoritmos do melhor para o pior: 
1. Algoritmo D (melhor algoritmo – mais rápido); 
2. Algoritmo B; 
3. Algoritmo C; 
4. Algoritmo A (Pior algoritmo). 
 
Gráfico de cada um dos quatro algoritmos: 
Algoritmo A 4,5 10 20 48 148 536 2076 8224 32804 131112 
Algoritmo B 70 90 110 130 150 170 190 210 230 250 
Algoritmo C 20 46 88 146 220 310 416 538 676 830 
Algoritmo D 120 140 151,6993 160 166,4386 171,6993 176,1471 180 183,3965 186,4386 
Algoritmo A 
Algoritmo B 
5 
 
 
Algoritmo D 
Algoritmo C 
Todas os algoritmos em um só gráfico 
6 
5. (10 pontos) Um algoritmo realiza n2 + 2n+2 operações primitivas até terminar, no 
pior caso. Determine a sua complexidade (taxa de crescimento) usando a 
notação O. Explique como você chegou a esse resultado. 
 R: Dentre as operações informadas acima, o termo de maior grau é o que mais 
impacta na taxa de crescimento, que nesse caso trata-se da função exponencial. Então, 
para se determinar a taxa de crescimento do algoritmo mencionado, devemos deixar de 
lado a função quadrática (pois possui um menor grau), levando em consideração apenas 
a função expoencial com a remoção dos valores constantes, que é o caso do número dois 
que está sendo somando com n no expoente. Dessa forma, a taxa de crescimento é 
O(2n). 
 
6. (10 pontos) Ordene as funções a seguir pela ordem de complexidade: n2, n, log2n, 
2n, nlog2n, n3. 
 Ordenação das funções da menos complexa para a mais complexa: 
1. log2n (menos complexa); 
2. n; 
3. nlog2n; 
4. n2; 
5. n³; 
6. 2n (mais complexa).
7 
8 
 
7. (10 pontos) Para cada uma das equações a seguir, determine sua complexidade 
usando a notação O. 
(a) 2
n 
+ 2n -> O(2n) 
(b) 10n + 50 -> O(n) 
(c) 10 + 2n2 + n -> O(n²) 
(d) 100 + 20log2n -> O(log2n) 
(e) 50n + 2n + 200 -> O(2n) 
(f) 1000 + 3nlog2n + 300n -> O(nlog2n) 
(g) log2n + 5n -> O(n) 
(h) n2 − 400n + 50n3 -> O(n³) 
 
8. (10 pontos) Considere 5 diferentes algoritmos que resolvem o mesmo problema. 
Todos os algoritmos levam 5s (cinco segundos) para terminar com uma entrada de 
tamanho 40. Após realizar uma análise você descobriu que cada algoritmo possui 
uma complexidade diferente. Determine em quanto tempo cada algoritmo termina 
para uma entrada de tamanho 80, considerando as seguintes complexidades: 
(a) 1 -> 5 
(b) log2n -> 5,939509123545537 
(c) n -> 10 
(d) n2 -> 20 
(e) 2n -> 5497558138880 
 
9. (10 pontos) Considere 4 diferentes algoritmos que resolvem o mesmo problema. 
Todos os algoritmos levam 2s (dois segundos) para terminar com uma entrada de 
tamanho 10. Após realizar uma análise você descobriu que cada algoritmo possui 
uma complexidade diferente. Determine o tamanho da entrada para que o 
algoritmo termine em 15 segundos, considerando as seguintes complexidades: 
(a) n -> 75 
(b) log2n -> 31622777 
(c) n2 -> +- 27 
(d) 2n -> +- 13