ATPS

Análise e Complexidade de Algoritmos

CIÊNCIA DA COMPUTAÇÃO

Alunos:
Ricardo Granusso Sanfelice RA: 1001760026
Paulo Henrique Pereira RA: 1042104192

Sumario
Etapa 1 3
Passo 2 3
Passo 3 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 4
Etapa 2 5
Passo 1 5
Selection sort 5
Insertion sort 5
Passo 2 5
Passo 3 6
Passo 4 6
Etapa 3 8
Passo 1 8
Passo 2 8
Passo 3 9
Etapa 4 10
Pesquisa 10
Etapa 5 11
Passo 1 11

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
1.)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

2.)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

3.)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);