analise e complexidade de algoritmos

ATPS - 7ª Série

Professor: Murilo de Lima

Indaiatuba, 10 de Abril de 2014.

ETAPA 1:

Aula-tema: Medidas de Complexidade, análise assintótica de limites de complexidade.

Essa atividade é importante para que você conheça as medidas assintóticas de complexidade, considerando que os algoritmos são representados, muitas vezes, por funções matemáticas, assim, faz-se um estudo sobre o comportamento assintótico dessas funções.
Para realizá-la, é importante seguir os passos descritos.

Passos: 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.

Complexidade ômega Ω, theta θ e ômicron O são usados para medir o custo computacional de um algoritmo à medida que a entrada aumenta e exposto em termos de uma função.

Complexidade Ômega (Ω)

- Melhor Caso:
É o menor tempo de execução em uma entrada de tamanho n.
É pouco usado, por ter aplicação em poucos casos.

- Exemplo:
Numa lista de n números para encontra-los, assume-se que a complexidade no melhor caso é f(n) = Ω(1), pois se assume que o número estaria logo na topo da lista.

Complexidade Theta (θ)

- Caso Médio:
Dos três, é o mais difícil de determinar, devendo-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.

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
Muito difícil de determinar na maioria dos casos

- Exemplo: f(n)=Ɵ(n/2) Complexidade Ômicron (O)

- Pior Caso:
Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n.

- Exemplo:
Se tivermos uma lista de n números e