Análise do algoritmo

Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações

Trabalhos Gratuitos

Trabalho Completo Analise De Algoritmo

Analise De Algoritmo

Imprimir Trabalho!

Cadastre-se - Buscar 155 000+ Trabalhos e Monografias

Categoria: Tecnologia

Enviado por: jeurides 08 junho 2013

Palavras: 706 | Páginas: 3

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 n é 20, O(2n) é um milhão

Função cúbica esse algoritmo é parecido com quadrática pois esse trabalha de forma em três em três quando o quadrática trabalha de forma dois em dois, esse algoritmo Cúbica trabalha de forma de loop dentro de mais dois loop,e útil para resolver problemas pequenos

Exemplo: multiplicação de matrizes

Função exponencial f(n) = 3

Função cúbica g(n) = n³+2n

f(n) =3

g(n) = n³+2n

f(n)Ω(g(n))?

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

3. Comparar duas funções quadráticas f(n) e g(n) e mostrar que f(n) é Theta (g(n)),

determinando