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