Gabarito Tema 3 - Complexidade de Algoritmos

Prévia do material em texto

Exercícios de Fixação 
TEMA 3 : COMPLEXIDADE DE ALGORITMOS
PROFESSOR : ROGÉRIO MALHEIROS DOS SANTOS
1) Dada uma Entrada de Tamanho N para um Algoritmo dado :
a)O Que é a Complexidade de Melhor Caso? É a Função dada pelo caso em que ocorre o menor 
número de operações possível
b)O que é a Complexidade de Caso Médio? É a Função dada pela soma dos produtos p(i)n(i) 
onde n(i) é o número de operações no Caso i e p(i) é a probabilidade de ocorrer no Caso i
c) O que é a Complexidade de Pior Caso? É a Função dada pelo caso em que ocorre maior 
número de operações possível
2) Qual é o Melhor Caso no Algoritmo de Busca Sequencial e qual sua ordem de Complexidade?
O Melhor caso é quando o número a ser procurado encontra-se na primeira componente do 
vetor. Neste caso a ordem é O(1)
3) Qual é o Pior Caso no Algoritmo de Busca Sequencial e qual sua ordem de Complexidade?
O Pior caso é quando o número a ser procurado não encontra-se no vetor. Neste caso a ordem 
é O(n)
4) Qual é a função de Complexidade de Caso Médio do Algoritmo de Busca Sequencial quando o 
valor a ser encontrado está no vetor com certeza e a probabilidade de achá-lo é igual (uniforme) em 
cada posição do vetor?No caso particular de n = 13, qual o valor da função de Complexidade?
 
f(n)= n +1 No caso de n=13 dá (13+1)/2 = 7 
 2 
5) Qual é a função de Complexidade de Caso Médio do Algoritmo de Busca Sequencial quando o 
valor a ser encontrado tem 50% de chance de não estar no vetor e 50% de estar no vetor e a 
probabilidade de achá-lo é igual (uniforme) em cada posição do vetor?No caso particular de n = 13, 
qual o valor da função de Complexidade?
f(n)= 3n +1 No caso de n=13 dá (3 x 13+1)/2 = 10 
 4 
6) O Algoritmo de Busca Binária pode ser utilizado em qualquer vetor?Justifique a sua resposta
Não. Ele só pode ser utilizado em vetores ordenados (Problema de Busca Ordenada)
7) Seja o vetor ordenado v = (2 , 7, 9 ,12 ,15,25,30) . Se o valor a ser encontrado no vetor for o 
número 15 em quantas iterações o Algoritmo de Busca Sequencial achará o valor no vetor v? 
Justifique a sua resposta
O Algoritmo de Busca Sequencial fará a busca começando do valor 2 depois o valor 7 depois o
valor 9 depois o valor 12 e finalmente chegando no valor 15 fazendo neste caso 5 iterações 
para achar o número 15
8) Seja o vetor ordenado v = (2 , 7, 9 ,12 ,15,25,30) . Se o valor a ser encontrado no vetor for o 
número 15 em quantas iterações o Algoritmo de Busca Binária achará o valor no vetor v?Justifique 
a sua resposta
O Algoritmo de Busca Sequencial fará a busca começando do valor central do 12 .Depois 
sabendo que 15>2 ele irá para o valor central dentro dos valores à direita de 12 (15,25,30) que 
é 25. Depois sabendo que 15<25 ele irá no valor que restou à esquerda de 25 finalmente 
chegando no valor 15 fazendo neste caso 3 iterações para achar o número 15
9) Qual é o Melhor Caso no Algoritmo de Busca Binária e qual sua ordem de Complexidade?
O Melhor caso é quando o número a ser procurado encontra-se na parte central do vetor. 
Neste caso a ordem é O(1)
10) Qual é o Pior Caso no Algoritmo de Busca Binária e qual sua ordem de Complexidade?
O Pior caso é quando o número a ser procurado não encontra-se no vetor. Neste caso a ordem 
é O(log n)