Atps - Analise De Algoritmos

Faculdade Anhanguera de Anápolis

Ciência da Computação - 7º semestre

Atividade Prática Supervisionada

Professor: Pedro Manoel

Alunos: Adenilson Pereira Lima - RA 1157383360

Daniel Couto Marques - RA 2504084730

Mateus Brasil Miranda - RA 1108361889

Paulo Augusto Gomes Costa - RA 2504085504

Análise e Complexidade de Algoritmos

Anápolis – 2014

Estudo sobre análise de classes distintas de algoritmos

Etapa 1

Ômicron (O) - Consiste no maior tempo de execução sobre todas as entradas de tamanho N. Ex: Se tivermos uma lista de N números e quisermos encontrar algum deles, assume-se que a complexidade no pior caso é O (N), pois assume-se que o número estaria, no pior caso, no final da lista.

Ômega (Ω) - É o menor tempo de execução em uma entrada de tamanho N, mas é pouco utilizado, por ter aplicação em poucos casos. Ex: Se tivermos uma lista de N números e quisermos encontrar algum deles assume-se que a complexidade no melhor caso é f(N)=Ω(1), pois assume-se que o número estaria logo na cabeça da lista.

Theta (Ө) – Este obtém o tempo médio de execução em uma entrada de tamanho N, ou baseado em probabilidade de determinada condição ocorrer, e é o mais difícil de se determinar.

Atividades

1. Comparar uma função linear F(N) com uma função quadrática G(N) e mostrar que F(N) é Ômicron (G(N)), determinando constantes N0 natural e C real positivo.

Função linear de F(N) = 3N+(2,5)

Função quadrática G(N) = 2N²