Trabalho Analise de Algoritmo

UNIVERSIDADE PRESIDENTE ANTÔNIO CARLOS – UNIPAC
FACULDADE REGIONAL DO VALE DO AÇO - FARV CURSO DE CIÊNCIA DA COMPUTAÇÃO

LORENA ARAUJO CARVALHO

I LISTA DE EXERCÍCIOS
ANÁLISE DE ALGORITMOS

IPATINGA
2013

LORENA ARAUJO CARVALHO

ANÁLISE DE ALGORITMOS

I Lista de Exercício Interdisciplinar apresentado à disciplina de AA (Análise de Algoritmos) do Curso de Ciência da Computação da Universidade Presidente Antônio Carlos – UNIPAC – Faculdade Regional do Vale do Aço – FARV como requisito parcial para atividades interdisciplinares do curso. Orientador: Felipe Fernandes

IPATINGA 2013

"Medir o progresso de um programa por linhas de código é como medir o processo de montagem de um avião pelo peso."

Bill Gates

1) Significa dizer que se fossem realizados experimentos com este algoritmo, seria constatado que o seu tempo de execução, para qualquer entrada seria de tamanho n, ou seja independente do tamanho, o resultado é o log do tamanho dele.

2) O(1) E O(10), não há diferença, pois nesse caso qualquer constante é desprezível. O fato de ignorarmos os fatores constantes ocorre consequencia de estarmos interessados nos casos em que o tamanho da entrada* é suficientemente grande, ou quando "n" tende a infinito.
Tamanho de entrada* - quantidade de espaço requerido para armazenar entrada.

3) Dependerá do tamanho do problema. Terei Teremos n5> 2n para n < 23, portanto 2n é melhor ; para n >= 23, n5 é melhor. No limite, uma complexidade polinomial é melhor que uma complexidade exponencial para problemas “grandes”.

4) Não existirá valores de “n” que satisfaça a condição, pois qualquer valor que atribuirmos a “n”, ele nunca irá fazer A ser mais rápido, pelo devido fato de a função A(n)= n² - n=549. A sempre será maior que B (nestas condições).

5)