- Escreva um algoritmo que recebe um conjunto de “N” valores, uma chave “k” e retorna a
quantidade de ocorrências de “k” encontradas. Caso a chave não esteja presente no conjunto, o
algoritmo deve retornar o valor 0. Considerando o algoritmo definido por você, responda ao que se
pede:
a) Em que situação ocorre o melhor caso?
b) Em que situação ocorre o pior caso?
c) Calcule a fórmula do tempo de execução T(n) do algoritmo para uma entrada de tamanho n.
d) Mostre através de um loop invariante que seu algoritmo é correto. Lembre-se de (I) enunciar a
propriedade do loop e mostrar que ela é verdadeira (II) antes do loop iniciar, (III) após a execução
de uma iteração i e (IV) após o término do laço
Você diz que não quer resposta pronta e não diz qual é sua dúvida, apenas copia e cola a questão. Assim fica difícil, né?
Eu fiz aqui para achar a posição do vetor um exercício semelhante a este , só que agora ele pede para contar as posições e definir o loop invariante no seu melhor e pior caso
Ora é praticamente o mesmo algoritmo, a diferença é que vc vai ter que ir até o fim do vetor, uma vez que vc não pode assumir nada sobre o mesmo.
se o vetor estivesse ordenado seria trivial descobrir como parar (e como procurar, via busca binaria ).
inclusive se o vetor tiver alguma ordenação os valores vão estar todos proximos, isso talvez seja um “melhor caso”. reflita sobre isso
1 curtida
Olha o jeito que eu fiz 
Algoritmo conta ocorrências
Início
cont =0;
Busca( vetor V, chave K)
para i <- 1 até n faça
Se vetor[i]= k
retorna
cont = cont +1
fim se
fim para
retorna pos =-1;
fim algoritmo