ATPS Analise E Comlexidade De Algoritmos

SUMÁRIO

1 PRIMEIRA ETAPA 3

1.1 Melhor Caso 3

1.2 Pior Caso 3

1.3 Caso Médio 3

1.4 Comparação de função linear f(n) com função quadrática g(n) 4

1.5 Comparação de função exponencial f(n) com uma função cúbica g(n) 4

1.6 Comparação de duas funções quadráticas f(n) e g(n) 5

1.7 Algoritmo 5

2 Segunda Etapa 7

2.1 Vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção. 7

2.1.1 Ordenação por Seleção (SELECTION SORT) 7

2.1.2 Ordenação por Inserção (INSERTION SORT) 7

2.2 Criação de um algoritmo de ordenação por inserção e um de ordenação por seleção. 8

2.2.1 Ordenação por Inserção 8

2.2.2 Ordenação por Seleção 8

Referências Bibliográficas 10

1 PRIMEIRA ETAPA

1.1 Melhor Caso

• Definido pela letra grega Ω (Ômega).

• Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n.

• Exemplo: f(n) = Ω(1)

1.2 Pior Caso

• Representado pela letra grega Ο (Ômicron).

• Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n.

• É o método mas fácil de se obter.

• Exemplo: f(n) = 0(1)

1.3 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.

• Exemplo: f(n) = Ɵ(n/2)

1.4 Comparação de função linear f(n) com 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 é Ο(g(n)).

1.5 Comparação de 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 todo n ≥ 5f é Ω(g(n).

1.6 Comparação de 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²

Ο ≤ c1 f(n) ≤ g(n) Ο ≤ g(n) ≤ c2 f(n)

1.7 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.Item[i] = x then

achou := true;

end;

if achou then

pos := i

else

pos := -1;

2 Segunda Etapa

2.1 Vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção.

2.1.1 Ordenação por Seleção (SELECTION SORT)

É um algoritmo que percorre todos os itens restantes na pesquisa até encontrar o menor deles, para assim ordená-los. No selection sort para completar a ordenação você obrigatoriamente passa por todas as possibilidades de pesquisa.

No primeiro passo o maior valor é encontrado e posicionado como último item. No segundo passo você faz uma varredura nos elementos até o penúltimo, pois o ultimo já esta ocupado pelo maior valor. Desse itens pesquisados o maior encontrado é substituído pelo penúltimo. Este