Atps análise e complexidade de algoritmos

FACULDADE ANHANGUERA DE TAUBATÉ – UNIDADE II

Análise e Complexidade de Algoritmos
Prof. Fernando Salles Claro

Atividade Prática Supervisionada

Curso: Ciência da Computação
Semestre: 1º - Turma A – Ano: 2012/1

Etapa 1

Melhor Caso

* Definido pela letra grega Ω (Ômega). * Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n. * Ex: f(n)=Ω(1)

Pior Caso * Representado pela letra grega 0 (Ômicron). * Baseia-se no maio tempo de execução sobre todas as entradas de tamanho n. * É o método mas fácil de se obter. * Ex: f(n)=0(1)

Caso Médio * Definida pela letra grega Ɵ(Theta) * Deve- se obter a média dos tempos de execução de todas as entradas de tamanho n, ou baseado em probabilidade de determinada condição ocorrer. * Ex: f(n)=Ɵ(n/2)

Comparar uma função Linear f(n) com uma função Quadrática g(n). * Função Linear f(n) = 5n +2 * Função Quadrática g(n) = 2n²

f(n)= 5n+2 g(n)=2n² f(n) é o(g(n))?

Para n ≥ 3 é o(g(n)).

Comparar uma função exponencial f(n) com uma função cúbica g(n). * Função exponencial f(n) = 2n n * Função cúbica g(n) = n³+2n

f(n)=2n n g(n)= n³+2n f(n)Ω(g(n))? Para n ≥ 5 é Ω(g(n).

Comparar duas funções quadráticas f(n) e g(n). * Função quadrática f(n) = n²+4+3n * Função quadrática g(n) = 5n²+3² o ≤ c1 f(n) ≤ g(n) o ≤ g(n) ≤ c2 f(n)

Crie um Algoritmo.

Procedure Verifica_Item_Lista (Lista: TipoLista; x: TipoItem; pos: integer);
Var i: integer;
Begin
I: = 1; achou := false; While (i <= Lista.Tamanho) and not achou do begin inc(i); if Lista.Intem[i] = then achou := true; end; if achou then pos := i else pos := -1;

Etapa 2 Cite as vantagens e desvantagens dos algoritmos de ordenação por