1 Lista De Exercícios De Estrutura De Dados

1ª Lista de Exercícios de Estrutura de Dados

1. Explique o que significa análise assintótica de algoritmos.
2. Quais são, em geral, as duas medidas de eficiência para análise de algoritmos? 3. Vamos supor que estamos comparando implementações de ordenação por inserção e ordenação por intercalação na mesma máquina. Para entradas de tamanho n, a ordenação por inserção é executada em 8n² etapas, enquanto a ordenação por intercalação é executada em 64n Ig n etapas. Para que valores de n a ordenação por inserção supera a ordenação por intercalação?
4. Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n² funciona mais rápido que um algoritmo cujo tempo de execução é 2n na mesma máquina?
5. Para cada função f(n) e cada tempo t na tabela a seguir, determine o maior tamanho n de um problema que pode ser resolvido no tempo t, supondo-se que o algoritmo para resolver o problema demore f(n) microssegundos. L g n
√
n nl g n N
²
N
³
2 n n
!

1

1

1

1

1

1

1

s e g u n d o

m i n

h o r a d i a

m ê s

a n o

s é c u l o 6. Faça uma comparação entre todos os métodos de ordenação estudados em aula, com relação à ordem de complexidade (melhor caso, caso médio e pior caso e complexidade do algoritmo).
7. Explique por que o algoritmo da bolha melhorado funciona melhor que o algoritmo da bolha tradicional.