Conceitos básicos de Complexidade e avaliação

Anotacoes

ISUPE EKUKUI II Curso: Engenharia Informática Ano Curricular: 2o Disciplina: EDA II Sumario: Complexidade Algoritmica. Estudo de casos melhor/médio/pior. Complexidade Algoritmica. Diferentes computadores, muitas vezes com hardwares idênticos, podem levar tempos diferentes para processar um mesmo algoritmo; – Quando trocamos algum, ou mais, itens de hardware, esta diferença tende a aumentar ainda mais; • Por tanto, avaliar o desempenho de um algoritmo com base apenas no tempo de exe cução deste, é ineficiente. Surge o conceito de Complexidade de Algoritmos; A Complexidade de Algoritmos estuda e define quanto eficiente é um algoritmo em re lação ao número de operações (passos do algoritmo) necessárias para finalizar a tarefa. A avaliação de desempenho de um algoritmo quanto executado por um computador pode ser feita a posteriori ou a priori. Uma avaliação a posteriori envolve a execução propriamente dita do algoritmo, medindo se o tempo de execução. Só podendo ser exata se forem conhecidos detalhes da arquite tura da máquina, da linguagem de programação usada, do código gerado pelo compi lador, etc. De fato, o tempo deve ser medido fisicamente para um certo algoritmo, compi lador e c...