O algoritmo abaixo opera sobre um vetor A[1 . . n]. Quantas atribuições ele faz no pior caso? Quantas comparações?
O algoritmo abaixo opera sobre um vetor A[1 . . n]. Quantas atribuições ele faz no pior caso? Quantas comparações?
1 s ← 0
2 para i ← 1 até n faça
3 s ← s + A[i]
4 m ← s/n
5 k ← 1
6 para i ← 2 até n faça
7 se (A[i] − m)2 < (A[k] − m)2
8 então k ← i
9 devolva k
💡 4 Respostas
Thiago Bucalon
No pior caso será n² porque ele nunca irá entrar no if e assim deverá executar os dois for até o fim.
Andre Smaira
Para esse caso teremos as seguintes atribuições:
T(n) = 2T(n/2) + n³
Árvore de recursão
n³
n³
--------->
T(n/2) T(n/2)(n/2)³(n/2)³
T(n/4)T(n/4)T(n/4)T(n/4)
n³____ n³
h = log n
(n/2)³(n/2)³____n³/4
T(n/4)T(n/4)T(n/4)T(n/4)____n³/16
n³/1-(1/4) ==> n³/3/4 ==> 4n³/3 ==> Theta(n³)
Andre Smaira
Para esse caso teremos as seguintes atribuições:
T(n) = 2T(n/2) + n³
Árvore de recursão
n³
n³
--------->
T(n/2) T(n/2)(n/2)³(n/2)³
T(n/4)T(n/4)T(n/4)T(n/4)
n³____ n³
h = log n
(n/2)³(n/2)³____n³/4
T(n/4)T(n/4)T(n/4)T(n/4)____n³/16
n³/1-(1/4) ==> n³/3/4 ==> 4n³/3 ==> Theta(n³)
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Perguntas relacionadas
Materiais relacionados
3 pág.
Compartilhar