Analise e Complexidade de Algoritmos Atps 2015

Analise e Complexidade de Algoritmos

Etapa -1
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).
Resumo

Varios Critérios podem ser usados para a construção de um algoritmo e escolher se vai depender estarem selecionados para sua utilização ou somenti um experimento para um programa de grande utilização ou que também possa ser utilizado poucas vezes tendo algumas alterações no código. Um jeito simples de solucionar um algoritmo é quando existem vários tipos de solução para um resposta que possa ser um algoritmo de fácil entendimento e codificação que fassa um uso eficiente de seus recursos no computador. Uma medida para calcular uma complexidade de algoritmo é que pode se medir inúmeros passos de execução em um modelo matemático, ou também numero de segundos gastos em um computador especifico. Calculando os tempos de execução nas maquinas especificas, a maioria das analises acabam sendo contadas pelos números de operações que são executadas e a medida de complexidade e crescimento dessas operações. Um algoritmo resolve o problema quando para qualquer entrada produz uma resposta correta, mesmo desenvolvendo um problema o algoritmo pode ou não ser aceitável na pratica por requerer muito espaço e tempo. Um problema é considerado INTRATÀVEL se não existe um algoritmo para ele cuja demanda de recursos computacionais seja razoável.

Passo -2)
A medida de complexidade Ômicron, ou o pior caso, é representado pela letra grega 0 e baseia-se no maior tempo de execução entre todas as entradas.Ex.: O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = O(n).Por sua vez, a medida de complexidade ômega, representada pela letra grega
Ω
, representa o melhor caso, onde exprime o menor tempo de execução de um algoritmo para uma entrada n. Definir de acordo com o texto lido no passo um podemos dize que as medidas de complexidade

Ômicron (O), Ômega (Ω) e Theta (θ).

Melhor caso

Definido pela