ATPS Etapa 1 E 2 Analise E Complesidade De Algoritmos

Etapa 1

Passo 2

Definir de acordo com o texto lido no passo 1, as medidas de complexidade

Ômicron ( O ), Ômega ( Ω ) e Theta ( Ɵ ).

Melhor Caso

Definido pela letra grega Ω (Ômega).

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

Ex: f(n)=Ω(1)

Pior Caso

Representado pela letra grega 0 (Ômicron).

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

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

Ex: f(n)=0(1)

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.

Ex: f(n)=Ɵ(n/2)

Passo 3

1. Comparar uma função Linear f(n) com uma função Quadrática g(n) e mostre que f(n) é Ômicron (g(n)), determinando constantes n0 natural e c real positivo;

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 é o(g(n)).

2. Comparar uma função exponencial f(n) com uma função cúbica g(n) e mostre que f(n) é Ômega (g(n)), determinando constantes n0 natural e d real positivo;

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 n ≥ 5 é Ω(g(n).

3. Comparar duas funções quadráticas f(n) e g(n) e mostre que f(n) é Theta (g(n)), determinando constantes c, d reais positivos e n0 natural.

Função quadrática f(n) = n²+4+3n

Função quadrática g(n) = 5n²+3²

o ≤ c1 f(n) ≤ g(n)

o ≤ g(n) ≤ c2 f(n)

Passo 4

Criar um algoritmo que tenha pelo menos dois elementos que sejam comuns a maioria dos algoritmos como, por exemplo, atribuições simples, declarações, laços, laços aninhados, If-Then-Else.

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;

Etapa 2

Passo1

Citar as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção. Explicar o funcionamento de cada um deles

Ordenação por Seleção (SECTION SORT)

É um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar o menor deles e movê-lo para uma posição final. A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles.

Funcionamento

O processo repete-se até que todos os elementos do array estejam ordenados

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

É um algoritmo eficiente para ordenar um pequeno número de elementos. Basicamente, este algoritmo varre um array de elementos da esquerda para a direita e a medida que avança vai deixando os elementos mais a esquerda ordenados.