Sistemas Distribuidos

Análise e Complexidade de Algoritimos

Passo 1 (Aluno)

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 (Equipe)

Definir, de acordo com o texto lido no passo 1, as medidas de complexidade Ômicron ( O), Ômega (Ω) e Theta (θ)

Ômega (Ω)

- Melhor Caso

Esse algoritmo executa em menor tempo um valor de tamanho N, é pouco utilizado por ter aplicações em poucos casos.

O algoritmo assume que o número procurado seria o primeiro selecionado na lista.

Ex: f(n)=Ω(1)

Theta (θ )

Caso Médio

Deve-se obter a média dos tempos de execução de todas as entradas de tamanho n, ou baseado em probabilidade de determinada condição ocorrer:

Em média será necessário visitar n/2 elementos do vetor até encontrar o elemento procurado

- Melhor aproximação

- Muito difícil de determinar na maioria dos casos

Ex: f(n)=Ɵ(n/2)

Ômicron (O)

Esse processo por sua vez é mais utilizado por ser mais fácil, obter os resultado, pois ele se baseia no maior tempo de execução sobre as entrada no tamanho N.

No pior caso será necessário visitar todos os n elementos do vetor até encontrar o elemento procurado.

É o método mas fácil de se obter.

Ex: f(n)=0(1)

Passo 3 (Equipe)

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;

Linear : Ele faz um busca em cada elemento entrada, essa forma é mais simples, pois ele só é indicada em pequenos algoritmos.

Quadrática : Esse algoritmo trabalha de forma que faz um loop dentro de outro Loop ou seja ele processa de forma em dois em dois, esse algoritmo é indicado em médio para pequenos algoritmos.

2. Comparar uma função exponencial f(n) com uma função cúbica g(n) e mostrar que f(n) é Ômega (g(n))

Exponencial : Ela é considerada um algoritmo de muita força, pois se utiliza de uma abordagem simples para resolver determinados processos.

Cúbica : Esse algoritmo é parecido com quadrática pois esse trabalha de forma três em três quando o quadrática trabalha de forma dois em dois, esse algoritmo trabalha com loop dentro de mais dois loop.

Comparar uma função Linear f(n) com uma função Quadrática g(n).

* Função Linear f(n) = 5n +2

* Função Quadrática g(n) = 2n²

f(n)= 5n+2

g(n)=2n²

f(n) é o(g(n))?

Para n ≥ 3 é o(g(n)).

Comparar uma função exponencial f(n) com uma função cúbica g(n).

* Função exponencial f(n) = 2n n

* Função cúbica g(n) = n³+2n

f(n)=2n n

g(n)= n³+2n

f(n)Ω(g(n))?

Para n ≥ 5 é Ω(g(n).

Comparar duas funções quadráticas f(n) e g(n).

* 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)

Crie um Algoritmo.

O nosso algoritmo tem a funcionalidade de receber um array , e verificar qual é o maior numero desse array :

Inicio

{

Int array1[5], maior ;

for(int i = 0; i<=5; i++ )

{

Escreva(“Digite um numero”)

Leia(array1[i]);

}

for(int i = 0; i<=5; i++ )

{

If(array1[i]>array[i+1])

{

maior = array[i];

}

Else

{

maior = array[i+1];

}

}

Escreva(“Maior numero é ”+ maior);

} fim

Etapa 2

Cite as vantagens e desvantagens dos algoritmos de ordenação por seleção e de ordenação por inserção.

- Ordenação por Seleção

É um algoritmo que ordena itens verificando repetidamente os itens restantes para encontrar o menor deles e movê-lo para uma posição final. A idéia por trás do selection sort é que para ordenar N itens você tem que passar por todos eles.

1. No primeiro passo você encontra o maior valor, e então troca ele pelo último item. Assim o maior item está agora na posição N.

2. No segundo passo você faz uma varredura apenas nos N-1 elementos. O maior

...