Complexidade de algoritmos
2669 palavras
11 páginas
Estruturas de DadosAlgoritmos
Prof. Eduardo Alchieri
Algoritmos
(definição)
Sequência finita de instruções para executar uma tarefa
Executáveis com uma quantidade de esforço finita
Bem definidas e não ambíguas
Executáveis em um período de tempo finito
Um algoritmo pode ser escrito de muitas formas
Exemplo: em alguma linguagem natural
Porém, estamos interessados em algoritmos especificados com alguna precisão por meio de formalisno matemático adequado
Exemplo, linguagem de programação
Algoritmos
(definição)
Definição de Dijkstra
Dijkstra é um cientísta holandês que, dentre outras contribuições, propôs o algoritmo de Dijkstra
Encontra o caminho mais curto num grafo
Um algoritmo correponde a uma descrição de um padrão de comportamento, expresso em termos de um conjunto finito de ações.
Ex: comportamento de a+b para diferentes valores de a e b
Algoritmos
(definição)
Um algoritmo não representa, necessariamente, um programa de computador
Algoritmo: sequência de ações para resolver uma tarefa, ou ainda, um procedimento passo a passo para se chegar com sucesso a um fim
Programa: sequência de instruções em código para executar uma operação em um computador
Um algoritmo corretamente executado não resolve uma tarefa se:
For implementado incorretamente
Não for apropriado para a tarefa
Custo de Algoritmos
(análise)
Um algoritmo deve:
Executar o mais rápido possível
Funcionar corretamente
Utilizar a memória da melhor forma possível
A fim de sabermos mais sobre um algoritmo, podemos analisá-lo
Precisamos estudar as suas especificações e tirar conclusões sobre como a sua implementação (o programa) irá se comportar em geral.
Custo de Algoritmos
(análise)
Mas o que podemos analisar de um algoritmo ? Podemos determinar:
O tempo de processamento de um programa