Miniteste

6 views
Skip to first unread message

Solon Aguiar

unread,
Apr 8, 2011, 8:36:01 PM4/8/11
to atal-c...@googlegroups.com
Oi Pessoal,

Para quem não foi para a aula hoje, o miniteste está disponível no site da disciplina (página exercícios).

Até mais.

Solon Aguiar

Rafael Aquino de Carvalho

unread,
Apr 9, 2011, 11:24:11 AM4/9/11
to atal-c...@googlegroups.com, Solon Aguiar
não entendi essa pergunta
  • Qual o custo geral do algoritmo em relação a espaço utilizado?
como assim, espaço utilizado?



-----------
Rafael Aquino de Carvalho

Solon Aguiar

unread,
Apr 9, 2011, 11:39:28 AM4/9/11
to Rafael Aquino de Carvalho, atal-c...@googlegroups.com
Oi,

Essa questão refere-se a quantidade de memória que o algoritmo utiliza. Vocês precisam ver o que ele guarda em memória; como ele faz esse armazenamento e a partir daí será possível saber quanto de memória ele utiliza.

Tome como o exemplo o merge sort. As implementações mais comuns sempre utilizam listas auxiliares para fazer o merge. Como, no final, todos os elementos terão passado pelo menos uma vez por cada uma das listas, o custo geral de espaço é O(n).  Isso porque, ao final, cada elemento "passará" uma vez pela memória.

Até mais.

Solon Aguiar
2011/4/9 Rafael Aquino de Carvalho <rafael.aqui...@gmail.com>
Reply all
Reply to author
Forward
0 new messages