A Análise e Complexidade de Algoritmo
Por: Valmir Pinheiro • 4/4/2015 • Trabalho acadêmico • 4.111 Palavras (17 Páginas) • 401 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
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.
- 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 |
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)
- 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
...