Atps complexidade de algoritmos

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 1

Passo 2

A medida de complexidade Ômicron, ou o pior caso, é representado pela letra grega 0 e baseia-se no maior tempo de execução entre todas as entradas.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = O(n).
Por sua vez, a medida de complexidade ômega, representada pela letra grega Ω, representa o melhor caso, onde exprime o menor tempo de execução de um algoritmo para uma entrada n.
Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n)=Ω(1).
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.
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 |
|1 |5 |2 |
|2 |8 |13 |
|3 |11 |30 |

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