ATPS^ Análise e Complexidade de Algoritmos

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

if Lista.Item[i] = x then

achou := true;

end;

if achou then

Result := i

else

Result := -1;

Etapa 2

Passo 1

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 é funcionar bem em uma lista pequena. Além disso, 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. Assim como o bubble sort, ele exige n² números de passos para cada n elementos. Adicionalmente, o seu desempenho é facilmente influenciado pela ordem inicial dos itens antes do processo de triagem. Devido a isso, esse tipo seleção é adequado apenas para uma lista em que poucos elementos estejam em ordem aleatória.

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. É um algoritmo de ordenação de local, logo, o requerimento de espaço é mínimo. A desvantagem é que não possui um desempenho tão bom quanto outros algoritmos de ordenação. Com n² passos necessários para funcionar, o insertion sort também não funciona bem com listas grandes. No entanto, é particularmente útil com listas de poucos itens.

Passo 2

Ambos os algoritmos abaixo, foram desenvolvidos em Delphi.

Insertion Sort

procedure InsertionSort(data : array of integer; num_ele : integer);

var

i,j,temp: integer;

begin

...