ATPS Oficial Complexidade

Análise e Complexidade de Algoritmos

CIÊNCIA DA COMPUTAÇÃO

Alunos:
Ricardo Granusso Sanfelice RA: 1001760026
Paulo Henrique Pereira RA: 1042104192

Sumario
Etapa 1 3
Passo 2 3
Passo 3 3
1.)Função Linear f(n)=3n + 2 | Função Quadrática g(n) = 3n² + 2n -3 3
2.)Função Exponencial f(n)=n4 | Função cúbica g(n)=2n³ + n² - n + 2 3
3.)Função Quadrática f(n)=n²-n+2 | Função Quadrática g(n)=2n²-3n +2 3
Passo 4 4
Etapa 2 5
Passo 1 5
Selection sort 5
Insertion sort 5
Passo 2 5
Passo 3 6
Passo 4 6
Etapa 3 8
Passo 1 8
Passo 2 8
Passo 3 9
Etapa 4 10
Pesquisa 10
Etapa 5 11
Passo 1 11

Etapa 1
Passo 2

A medida de complexidade Ômicron, ou seja, o pior caso, é representado pela letra grega 0 e define que dado uma entrada de tamanho n o tempo de execução será o maior.
Ex.: f(n) = O (1).
Já a medida de complexidade ômega, é representada pela letra grega Ω, está representa o melhor caso, e define que dado uma entrada de tamanho n o tempo de execução será o menor.
Ex.: f(n)=Ω(1).
E por último temos o caso médio ou medida de complexidade Theta(θ), onde obtêm-se a média dos tempos de execução das entradas de tamanho n, esse calculo é realizado através da soma do melhor caso e o pior caso dividido por 2.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = θ(n/2)

Passo 3
1.)Função Linear f(n)=3n + 2 | Função Quadrática g(n) = 3n² + 2n -3 n f(n)=3n + 2 g(n) = 3n²+2n-3
5
17
82
10
32
317
15
47
702

2.)Função Exponencial f(n)=n4 | Função cúbica g(n)=2n³ + n² - n + 2 n f(n)=n4 g(n)=2n³ - n² + n + 2
1
1
4
2
16
16
3
81
50

3.)Função Quadrática f(n)=n²-n+2 | Função Quadrática g(n)=2n²-3n +2 n f(n)=n²-n+2 g(n)=2n²-3n +2
1
2
1
2
4
4
3
8
11

Passo 4

#define n=10;

int verifica_maior ();

int vetor[n], maior, num;

for(int i=0; i<=n; i++){

printf(“Digite uma sequencia de números: ”); scanf(“%d”,&vetor[1]); if(i==0)

maior=vetor[i];

}

for(int i=1; i<=n; i++){

if(vetor[i]>maior){