ATPS 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 seleção e de ordenação por inserção.

* Ordenação por Seleção (SECTION SORT)

É um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar o menor deles e movê-lo para uma posição final. A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles.

1. No primeiro passo você encontra o maior valor, e então troca ele pelo último item. Assim o maior item está agora na posição N.

2. No segundo passo você faz uma varredura apenas nos N-1 elementos. O maior dos itens é troca de posição com o item na posição N-1. Assim o maior de todos os itens está agora na última posição; O segundo maior na segunda maior posição.

3. Este processo é repetido, com um item sendo colocado na sua posição correta a cada vez.

4. Depois de N passos, a coleção inteira de dados está ordenada. Uma variação simples é encontrar o menor item a cada vez e colocá-lo na frente. Para