ATPS etapas 1 e 2 de Análise e Complexidade de Algoritmos

Relatório 1

Defina, de acordo com o texto lido no passo 1, as medidas de complexidade Ômicron(O) Ômega(Ω) e Theta(Ɵ).

Existem três escalas de complexidade:

• Melhor Caso
• Caso Médio
• Pior Caso

Nas três escalas, a função f(n) retorna a complexidade de um algoritmo com entrada de N elementos.

Melhor Caso: Definido pela letra grega Ω (Ômega), é o menor tempo de execução sobre todas as entradas possíveis (N entradas).

Caso Médio: Definido pela letra grega Ɵ (Theta), das três complexidades é o mais difícil de se determinar. Deve-se obter a média dos tempos de execução de todas as entradas possíveis (N entradas), ou baseado em probabilidade de determinada condição ocorrer. É necessário já ter o Melhor Caso e o Pior Caso para que seja feita a escala do Caso Médio.

Pior Caso: Representado pela letra grega O (Ômicron), é o método mais fácil de se obter. É o inverso do melhor caso, baseia-se no maior tempo de execução sobre todas as entradas possíveis (N entradas).

Use as medidas de complexidade descritas acima e faça as seguintes atividades:

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

f(n)=o(g(n))⇒para toda constante c>0 ocorre que f(n)< c g(n).

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

Para todo n ≥N⇒ existe uma constante k>0 tal que f(n) ≤ k g(n)

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

Para todo n ≥ N⇒ f(n) = O (g(n))

Relatório 2

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

Ordenação por Seleção: O método ordenação por seleção é eficiente e de fácil processamento, porém deve unicamente ser utilizado para pequenos arranjos.

Seu funcionamento:

1. O método seleciona o menor valor do vetor a ser organizado;
2. O menor valor do vetor irá trocar a sua posição com o primeiro item do vetor;
3. Será repetido os passos acima até que o vetor esteja organizado.

Se o primeiro elemento estiver desordenado em relação ao elemento que está sendo comparado, é feira a troca. Sendo assim, no final do arranjo teremos o menor valor (ou o maior dependendo de sua comparação) na posição inicial do vetor e assim, seus outros elementos subsequentemente na mesma ordem.

Exemplo:

Vetor: [9,5,1,7,6,2,4]

1 – [1,5,9,7,6,2,4 ]

2 – [1,2,9,7,6,5,4]

3 – [1,2,4,7,6,5,9]

4 – [1,2,4,5,6,7,9] – Vetor organizado.

Algoritmo do método Ordenação por Seleção:

voidSelecao(VetorA,intn){

int i,j,min,x;

        for(i=0;i<=n-2;i++){

                min=i;

                for(j=i+1;j<=n;j++){

                        if(A[j]

                                min=j;

                }

                x=A[min];

                A[min]=A[i];

                A[i]=x;

        }

}

Ordenação por Inserção: É o mais rápido se comparado aos outros métodos básicos (Bolha e Seleção).

O diferencial desde método é que ele consiste em ordenar o arranjo utilizando um sub-arranjo ordenado localizado em seu início, a cada passo, um novo elemento é acrescentado a esse sub-arranjo até que atinja o último elemento do arranjo, fazendo o vetor no final do processamento estar organizado.

Exemplo:

Vetor: [P, S, E, F, M, B]

1 – [P, S, E, F, M, B]

2 – [E, P, S, F, M, B]

3 – [E, F, P, S, M, B]

4 – [E, F, M, P, S, B]

5 – [B, E, F, M, P, S] – Vetor organizado.

Algoritmo do método Ordenação por Inserção:

...