Analise De Algoritmo

ETAPA 1

Passo 1

Leitura do livro do Ziviane Projeto de Algoritmos

Passo 2

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

Ômicron e o pior caso e como se nos fizessemos um algoritimo que a entrada estaria na ultima posição

Pior caso f(n) = n

Entrada f fila (a,d,h,u,f )

Ômega e o melhor caso e como se a primeira entrada já fosse achada logo na primeira posição

Melhor caso f(n) = 1

Entrada a fila ( a,f,t,y,i)

Theta e o caso médio será correspondente a media dos tempos de execução, ou baseado em probabilidade de determinada condição ocorrer.

Caso médio f(n) = (n+1) /2

Execução 1 =1 + execução 2=3 <> 1+3 / 2=2

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;

Função linear o algoritmo realiza um número fixo de operações sobre cada elemento da entrada melhor situação para um algoritmo que processa n elementos de entrada e produz n elementos de saída

Exemplo: busca sequencial, calcular fatorial.

for (int x=1; x < n; x++) O(n)

Função quadrática trabalha de forma que faz um loop dentro de outro Loop ou seja ele processa de forma em dois em dois.

Exemplos: ordenação (ineficiente), imprimir uma matriz.

for (int x=1; x < n; x++)

for y=1; (int y y < n; y++) O(n2)

Função Linear f(n) = 7n +5

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

f(n)= 7n+5

g(n)=3n²

Para n ≥ 3 é 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;

Função exponencial e típico de algoritmos que fazem busca exaustiva (força bruta) para resolver um problema

Não são úteis do ponto de vista prático

Quando