Analise e Complexidade de algoritmo

[pic 1]

Faculdade Anhanguera de Santa Bárbara

Nome: John William Pereira Coelho

Curso: Ciência da Computação

Disciplina: Analise e Complexidade de Algoritmos

Atividade: ATPS

Série: 7º

Prof: Thiago

Data: 18/03/2014

Etapa 1

Passo 2

Medidas de Complexidade

Ômega

Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n. 
f(n)=Ω(1)

Baseia-se no maio tempo de execução sobre todas as entradas de tamanho n. 
É o método mas fácil de se obter. 
f(n)=0(1) 

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. 
f(n)=Ɵ(n/2)

Passo 3

1.)Função Linear f(n)=3n + 2 | Função Quadrática g(n) = 3n² + 2n -3 3
2.)Função Exponencial f(n)=n4 | Função cúbica g(n)=2n³ + n² - n + 2 3
3.)Função Quadrática f(n)=n²-n+2 | Função Quadrática g(n)=2n²-3n +2 3

Passo 4

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; 
end; 
end; 

Etapa 2

Passo 1

Insertion Sort 

O insertion sort varre a lista repetidamente e, a cada vez, insere um item da sequência desordenada na posição correta. A principal vantagem da ordenação por inserção é a sua simplicidade, além de mostrar um bom desempenho em listas pequenas. A desvantagem é que não possui um desempenho tão bom quanto outros algoritmos de ordenação.

Selection Sort

O selection sort vasculha repetidamente a lista de itens, selecionando um elemento de cada vez e colocando-o na posição correta da sequência. A principal vantagem do selection sort por ser um algoritmo de ordenação de local, não precisa de armazenamento temporário além do necessário para guardar a lista original. A principal desvantagem é sua baixa eficiência em listas grandes. 

Passo 2

Ordenação por Inserção

Template

Void insertion(Item vetor[], int n){

For (nt = 1; I < n; i++){

Int j = I;

While ( j > 0 && vetir[j – 1] > vetor[j])

{

Swap(vetor[j – 1], vetor[j]);

j--;

}}}

Template

Void swap(Item &A, Item &B)

{ Item t = A ; A = B ; B = t; }

Ordenação por Seleção (Selection Sort) 

template

Void selection(Item vetor[], int n){

For (int i = 0; i < n; i++){

Int min = I;

For (int j = i+1; j < n; j++)

If (vetor[j] < vetor[min]) min = j;

Swap(vetor[i], vetor[min]);

...