TrabalhosGratuitos.com - Trabalhos, Monografias, Artigos, Exames, Resumos de livros, Dissertações
Pesquisar

A Análise e Complexidade de Algoritmo

Por:   •  4/4/2015  •  Trabalho acadêmico  •  4.111 Palavras (17 Páginas)  •  114 Visualizações

Página 1 de 17

[pic 1]

Danilo de Palma – RA: 3786737187

Valmir Pinheiro Pinto – RA: 3776742110

Guilherme Menon – RA: 3730710528

Ciência da Computação

ATPS

Análise e Complexidade de Algoritmo – 7º Série

Prof. Rodrigo Rocha

Valinhos, 04/04/2015

ETAPA 1

Ômicron ( Ο ), Ômega ( Ω ) e Theta ( Θ ), são usados para medir a complexidade de um algoritmo, sendo que:

Ômicron ( Ο ) é usado para medir o pior caso,  por exemplo, dado uma entrada de dados do tamanho n o tempo de execução desse dados será o mais alto.

Theta ( Θ )é usado para medir o caso mediano, que entre Ômicrom e o Ômega.

Ômega ( Ω ) é usado para medir o melhor caso, onde o tempo de execução de um dado do tamanho n é menor.

  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;

n

f(n)=6n+2

g(n)=n²

0

2,00

0,00

1

7,00

1,00

2

12,00

4,00

3

17,00

9,00

4

22,00

16,00

5

27,00

25,00

10

52,00

100,00

20

102,00

400,00

30

152,00

900,00

40

202,00

1600,00

50

252,00

2500,00

100

502,00

10000,00

[pic 2]

Função Linear f(n) = 6n +2
Função Quadrática g(n) = 2n²
f(n) é O(g(n))?

Desde que n ≥ 3 é 0 (g(n)).

  1. 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;

N

f(n)=2ⁿ

g(n)=n³+2n

0

1,00

0,00

1

2,00

3,00

2

4,00

12,00

3

8,00

33,00

4

16,00

72,00

5

32,00

135,00

10

1024,00

1020,00

20

1048576,00

8040,00

30

1073741824,00

27060,00

40

1099511627776,00

64080,00

50

1125899906842620,00

125100,00

100

1267650600228230000000000000000,00

1000200,00

...

Baixar como (para membros premium)  txt (13.5 Kb)   pdf (214.1 Kb)   docx (93 Kb)  
Continuar por mais 16 páginas »
Disponível apenas no TrabalhosGratuitos.com