Atps ACA

FACULDADE ANHANGUERA DE TAUBATÉ – UNIDADE II

Análise e Complexidade Algoritmos
Prof. Gisele Pires

ATIVIDADES PRÁTICAS
SUPERVISIONADAS

Curso: Ciência da Computação
Semestre: 6º/7º - Turma A – Ano: 2015/1
RA
Nome do Aluno
3730722044
Carolina Presotto
5833167165
Gabriel S. do Nascimento
5827174015
Helio Sulliwan G. V. Canettieri
3715656925
Ronilson Alessandro Ferreira

Etapa 1
Passo 1
Ler o Capítulo 1 – “Introdução”: Seção 1.3; subseções 1.3.1, 1.3.2, do livro do Ziviani (2005).

Passo 2
Definir, de acordo com o texto lido no passo 1, as medidas de complexidade
Ômicron (Ο ), Ômega (Ω ) e Theta (Ө ).

Melhor Caso: (Notação Ω) = f(n) Ω (1) a melhor instancia faz o algoritmo executar utilizando o menor tempo possível.
Pior Caso: (Notação Ο) = f(n) Ο(n) o maior tempo demorado pelo algoritmo para execução de uma instância.

Caso Médio: (Notação Ө) = f(n) a média de tempo que o algoritmo demora para executar determinado processo.

Passo 3
Usar as medidas de complexidade descritas acima e fazer as seguintes atividades:
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;

f(n) = Ο(g(n)) para toda constante real C> Ο ocorre que f(n)< C g(n), para todo n < N -> existe uma constante K> Ο tal que f(n) < K g(n), para todo n N => f(n) = Ο(g(n)).

2. 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;

f(n)= Ο(Cn),baseado em que tempo exponencial - se n dobra, o número de operações é elevado ao quadrado. g(n)= Ο(n3), sempre que n dobra o tempo de execução é multiplicado por 8. f(n)= Ο(Cn) Ω g(n)= Ο(n3)

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

R: C(n) = (n2.n) |2*1/2 = (Ө n2)
Passo 4
Criar um algoritmo que tenha pelo menos