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)  •  439 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

[pic 3]

Função exponencial f(n) = 2ⁿ
Função cúbica g(n) = n³+2n
f(n)Ω (g(n))?
Para n ≥ 5 é Ω (g(n)).

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

[pic 4]

n

f(n) = n²+10+5n

g(n) = 7n²+5²

0

10

25

1

16

32

2

24

53

3

34

88

4

46

137

5

60

200

6

76

277

7

94

368

8

114

473

9

136

592

10

160

725

Função quadrática f(n) = n²+10+5n
Função quadrática g(n) = 7n²+5²
o ≤ c1 f(n) ≤ g(n) o ≤ g(n) ≤ c2 f(n)

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

Fibonacci Interativo

intfibonacci_i(int n)

{

        int i, ant_1=1, ant_2=1, fibo;                //1

...

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