ATPS Analise e Complexidade de Algoritmo
Por: Valmir Pinheiro • 5/4/2015 • Trabalho acadêmico • 3.585 Palavras (15 Páginas) • 247 Visualizações
[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
Sumário Pag
Etapa 1 1
Passo2 1
Passo3 1
Passo4 3
Etapa 2 4
Passo1 4
Passo2 5
Passo3 6
Passo4 7
ETAPA 1
Passo2:
Ô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.
Passo3:
- 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)).
- 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)).
- 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 |
...