Analise de algoritmo

FACULDADE ANHANGUERA DE CAMPINAS - UNIDADE III
CIÊNCIA DA COMPUTAÇÃO
ANÁLISE E COMPLEXIDADE DE ALGORITMOS

ATPS - Atividades Práticas Supervisionadas
(Etapas 1 e 2)

Prof. Carlos Papotti

Clodoaldo dos Santos Carrero 1053002128 7ª Série
Márcia Maria Santos do Rosário 1011780117
Maycon Jéfferson Mascelloni 1001793128
Robson Buzois Marciotto 1033941409
William dos Santos Gomes 7866744

Campinas (SP), 09 de abril de 2013
RELATÓRIO 1 (Etapa 1)
Definição das medidas de complexidade (Passo 2)

Ômicron (0)
A medida de complexidade Ômicron representa o algoritmo de pior caso, ou seja, dada uma entrada de tamanho n o seu tempo de execução será o maior.
Ex: f(n) = 0 (1)

Ômega (Ω)
A medida de complexidade Ômega representa o algoritmo de melhor caso, ou seja, dada uma entrada de tamanho n o seu tempo de execução será o menor.
Ex: f(n) = Ω(1)

Theta (θ)
A medida de complexidade Theta representa o algoritmo de caso médio, ou seja, a média dos tempos de execução das entradas de tamanho n.
Ex: f(n)= θ (n/2)

Comparando as funções (Passo 3)
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;
Função Linear f(n) = 5n +2
Função Quadrática g(n) = 2n² f(n) é 0 (g(n))?
Desde que n ≥ 3 é 0 (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;
Função exponencial f(n) = 2ⁿ
Função cúbica g(n) = n³+2n f(n)Ω (g(n))?
Para n ≥ 5 é Ω (g(n)).
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.
Função quadrática f(n) = n²+4+3n
Função quadrática g(n) = 5n²+3² o ≤ c1 f(n) ≤ g(n) o ≤ g(n) ≤ c2 f(n)

Criando o algoritmo (Passo 4)
Criar um algoritmo que tenha pelo menos dois elementos que sejam comuns a maioria dos