Aula 02 PANA

Prof. Davi Morais
N584

Agenda
 Conceitos
 Critérios de escolha do algoritmo

 Medidas de complexidade
 Análise de complexidade

Conceitos
 Algoritmo: é, em geral, uma descrição passo a passo

de como um problema é solucionável. A descrição deve ser finita, e os passos devem ser bem definidos, sem ambiguidades, e executáveis computacionalmente.(Terada)  Instância do problema: Um entrada que satisfaz a quaisquer restrições impostas no enunciado do problema, necessária para se calcular a solução
 Correto: Para cada instância do problema, o algoritmo para com saída correta.

Conceitos
 Um problema pode ser resolvido por diversos

algoritmos
 Por exemplo...

 O que não quer dizer que ele seja aceitável na prática
Entrada

Algoritmo 01

Algoritmo 02

10

0.00001s

0.001s

20

0.00002s

1s

30

0.00003s

17.9 minutos

40

0.00004s

12.7 dias

50

0.00005s

35.7 anos

Conceitos
 Escolhemos um algoritmo para resolver algum problema,

considerando alguns critérios:





Corretude
Simplicidade do código
Consumo de memória
Tempo de processamento

 Através da análise de algoritmo sabemos a medida de

desempenho proporcional ao tempo de execução do algoritmo.  Por exemplo, medida de desempenho n = 10s, então n2 = 100s

Questão
 Os computadores estão em constante evolução, estão

cada dia mais rápidos. Ainda assim, é necessário calcular a complexidade?

Questão





Computador A: 1 bilhão de instruções por segundo
Computador B: 10 milhões de instruções por segundo
Algoritmo 1: 2n2
Algoritmo 2: 50nlogn

 Computador A com o Algoritmo 1:
2.(106)2
109

= 2000𝑠

 Computador B com o Algoritmo 2:

50.106𝑙𝑜𝑔106
= 30𝑠
7
10

Medidas de complexidade

Medidas de complexidade

Medidas de Complexidade
 Calcular a quantidade de operações elementares do algoritmo
 Adição
 Subtração
 Comparação ...
 A complexidade é calculada pelo número de vezes que a operação

fundamental é realizada.

 A medida de complexidade é o crescimento assintótico dessa