ATPS Analise e Complexidade de Algoritmos

FACULDADE ANHANGUERA DE CASCAVEL

ATPS de Analise e Complexidade de Algoritmo

Relatório desenvolvido pelo acadêmico:
Luiz Henrique Homenhuk, RA: 2400007024,

Na disciplina de Analise e Complexidade de Algoritmos, ministrado pelo professor Emerson, Sexta e Sétima fase do Curso de Ciência da Computação.

CASCAVEL – PARANÁ
2015
Etapa 1
Passo 2
A medida de complexidade Ômicron, ou o pior caso, é representado pela letra grega 0 e baseia-se no maior tempo de execução entre todas as entradas.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = O(n).
Por sua vez, a medida de complexidade ômega, representada pela letra grega Ω, representa o melhor caso, onde exprime o menor tempo de execução de um algoritmo para uma entrada n.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n)=Ω(1).
Por último temos o caso médio ou medida de complexidade Theta(θ), onde obtêm-se a média dos tempos de execução das entradas de tamanho n.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = θ(n/2)

Passo 3

Função Linear f(n)=3n + 2 | Função Quadrática g(n) = 3n² + 2n -3 n f(n)=3n + 2 g(n) = 3n²+2n-3
1
5
2
2
8
13
3
11
30
Função Exponencial f(n)=n4 | Função cúbica g(n)=2n³ + n² - n + 2 n f(n)=n4 g(n)=2n³ - n² + n + 2
1
1
4
2
16
16
3
81
50
Função Quadrática f(n)=n²-n+2 | Função Quadrática g(n)=2n²-3n +2 n f(n)=n²-n+2 g(n)=2n²-3n +2
1
2
1
2
4
4
3
8
11

Passo 4
Function Verifica_Item (Lista: TipoLista; x: TipoItem) : Integer;
Var
i: integer; achou : Boolean;
Begin
I : = 1; achou := false; While (i <= Lista.Tamanho) and not achou do begin inc(i); if Lista.Item[i] = x then achou := true; end; if achou then Result := i else Result := -1;

Etapa 2
Passo 1

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 é