analise de algoritimo

Custo de um algoritmo
 Determinando o menor custo possível para resolver problemas de uma dada classe, temos a medida da dificuldade inerente para resolver o problema.
 Quando o custo de um algoritmo é igual ao menor custo possível, o algoritmo é ótimo para a medida de custo considerada.
 Podem existir vários algoritmos para resolver o mesmo problema.
 Se a mesma medida de custo é aplicada a diferentes algoritmos, então é possível compará-los e escolher o mais adequado.
UFMG/ICEx/DCC

Medida do custo pela execução do programa em uma plataforma real
 Tais medidas são bastante inadequadas e os resultados jamais devem ser generalizados: – os resultados são dependentes do compilador que pode favorecer algumas construções em detrimento de outras;
– os resultados dependem do hardware;
– quando grandes quantidades de memória são utilizadas, as medidas de tempo podem depender deste aspecto.
 Apesar disso, há argumentos a favor de se obterem medidas reais de tempo. – Por exemplo, quando há vários algoritmos distintos para resolver um mesmo tipo de problema, todos com um custo de execução dentro de uma mesma ordem de grandeza.
– Assim, são considerados tanto os custos reais das operações como os custos não aparentes, tais como alocação de memória, indexação, carga, dentre outros.

Medida do custo por meio de um modelo matemático  Usa um modelo matemático baseado em um computador idealizado.
 Deve ser especificado o conjunto de operações e seus custos de execuções.
 É mais usual ignorar o custo de algumas das operações e considerar apenas as operações mais significativas.
 Por exemplo, algoritmos de ordenação:
– consideramos o número de comparações entre os elementos do conjunto a ser ordenado e ignoramos as operações aritméticas, de atribuição e manipulações de índices, caso existam.
UFMG/ICEx/DCC

Função de complexidade
 Para medir o custo de execução de um algoritmo é comum definir uma função de custo ou função de