Analise E Complexidade 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 algoritmos como, por exemplo, atribuições simples, declarações, laços, laços aninhados, If-Then-Else. Entregar ao professor o Relatório 1 com todos os passos descritos nessa etapa.

O algoritmo abaixo recebe 10 números e retorna o maior número.

int main (void) {

int vetor[10], maior, num ;

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

printf (“Digite um numero: ”);

scanf (“%d”, &vetor[i]);

if (i==0)

maior = vetor[i];

}

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

if(vetor[i]>maior){

maior = vetor[i];

}

}

}

RELATÓRIO 2 (Etapa 2)

Passo 1 (Equipe)

Citar as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção. Explicar o funcionamento de cada um deles.

Ordenação por seleção

Vantagens: É um algoritmo simples de se aplicar, tem um custo linear no tamanho da entrada para o número de movimentos de registros, é vantajoso para arquivos com registros muito grandes.

Desvantagens: Tanto no melhor caso e no pior caso o custo do tempo será mesmo, outra desvantagem é que o algoritmo não é estável, ou seja, os registros com chaves iguais nem sempre irão manter a mesma posição relativa de antes do inicio da ordenação.

Funcionamento: Simplesmente o algoritmo seleciona o menor número e passa para a primeira posição, sendo o segundo maior para a segunda posição e assim sucessivamente.

Ordenação por inserção

Vantagens: Realiza menor número de comparações entre algoritmos de ordenação O(n), quando o vetor está ordenado, e no seu pior caso, ou seja, quando todos os itens estão em ordem reversa ocorre o O(n²).

Desvantagens: Quando se tem um item sendo inserido devem-se mover todos os elementos maiores.

Funcionamento: O algoritmo percorre o vetor, da esquerda para direita e consequentemente vai deixando ordenado.

Passo 2 (Equipe)

Criar um algoritmo de ordenação por inserção e um de ordenação por seleção para ordenar um vetor de tamanho n.

Ordenação por inserção

Algoritmo de ordenação por inserção na linguagem Java.

public static void main(String[] args){

Scanner entrada = new Scanner(System.in);

int[] vetor;

int opcao;

for(int i=0; exit==false; i++){

System.out.println("Digite