Analise e Complexidade de Algoritmo

ETAPA 1

Passo 1

Ler o Capítulo 1 – “Introdução”: Seção 1.3; subseções 1.3.1, 1.3.2, do livro do Ziviani (2005).

Passo 2

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

Complexidade ômega Ω, theta θ e ômicron O são usados para medir o custo computacional de um algoritmo à medida que a entrada aumenta e exposto em termos de uma função.

Complexidade Ômega (Ω) - Melhor Caso: É o menor tempo de execução em uma entrada de tamanho n. É pouco usado, por ter aplicação em poucos casos.

Exemplo:

Numa lista de n números para encontra-los, assume-se que a complexidade no melhor caso é f(n) = Ω(1), pois se assume que o número estaria logo na topo da lista.

Complexidade Theta (θ) - Caso Médio:Dos três, é o mais difícil de determinar, devendo-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. 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: Em média será necessário visitar n/2 elementos do vetor até encontrar o elemento procurado. Muito difícil de determinar na maioria dos casos.

Exemplo:

f(n)=Ɵ(n/2) Complexidade Ômicron (O) - Pior Caso: Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n.

Exemplo:

Se tivermos uma lista de n números e quisermos encontrar algum deles, assume-se que a complexidade no pior caso é O(n), pois se assume que o número estaria no final da lista.

Esse processo por sua vez é mais utilizado por ser mais fácil, obter o resultado, pois ele se baseia no maior tempo de execução sobre as entrada no tamanho N.

No pior caso será necessário visitar todos os n elementos do vetor até encontrar o elemento procurado. É o método mais fácil de obter. f(n)=0(1)

Passo 3

Usar as medidas de complexidade descritas acima e fazer as seguintes atividades:

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

R= Função Linear faz uma busca em cada elemento entrada, essa forma é mais simples devido a trabalhar apenas em pequenos algoritmos. Função Quadrática trabalha criando um loop dentro de outro loop, processando de dois em dois. Esse algoritmo é indicado em médio para pequenos algoritmos.

f(n) é o(g(n)):

-Função Linear f(n) = n + 2

-Função Quadrática g(n) = n²

f(n)=n+2

g(n)=n²

logo é evidente que:

n+2≤n²

-n² + n ≤ - 2 -> n² - n ≥ 2

Para n ≥ 2 é o(g(n)).

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

R= Função Exponencial é considerada um algoritmo de muita força devido a utilizar uma abordagem simples para resolver determinados processos. Função Cúbica é parecida com quadrática pois esse trabalha de forma três em três quando o quadrática trabalha de forma dois em dois, esse algoritmo trabalha com loop dentro de mais dois loop.

f(n)Ω(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

logo é evidente que:

2n n ≤ n³+2n, e portanto:

Para n ≥ 5 é Ω(g(n).

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

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

-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. Entregar ao professor o Relatório 1 com todos os passos descritos nessa etapa.

RELATÓRIO 1

Procedure verifica _item_lista

(lista: tipolista; x; tipoitem; pos: integer);

Var i; integer;

Begin

I; =1;

Achou :=fale;

While (i a; j--) Verifica se na posição anterior do array é maior que 0 e se é maior que a posição seguinte ex: 4>0 && 4>2, e permanece no array ate que ambas codições sejam falsas

{

array[j + 1] = array[j]; Coloca o numero anterior na posição seguinte ex: {4,2,1,3} muda para {4,4,1,3}

array[j] = a; E por fim coloca o numero que foi armazenado neste caso o 2 na posição anterior ex: {4,4,1,3} para {2,4,1,3}

}

}

}

E faz isso até que o array seja ordenado por completo

- Método por Seleção:

Array{4,2,1,3};

public static void ordenar(int[] array) {

int index_min,

aux;

for (int i = 0; i < array.length; i++) { Começa comparando o primeiro numero