Atps ACA

1174 palavras 5 páginas
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

Relacionados

  • Patologia atividade de autodesenvolvimento aula 3
    2401 palavras | 10 páginas
  • Fisilogia humana do exercicio
    938 palavras | 4 páginas
  • ATPS
    702 palavras | 3 páginas
  • BASES FISIOLOGICAS DO MOVIMENTO HUMANO2222
    1106 palavras | 5 páginas
  • Fisiologia
    1173 palavras | 5 páginas
  • Acidos nucleicos
    3132 palavras | 13 páginas
  • Ciencias
    11693 palavras | 47 páginas
  • manual engenharia açucareira
    1429 palavras | 6 páginas
  • Bernoullini
    15348 palavras | 62 páginas
  • Mecanismo Geral Da Contra O Muscular
    769 palavras | 4 páginas