Aula 02 PANA

574 palavras 3 páginas
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

Relacionados

  • CALEND RIO ESCOLAR 2014 2015
    763 palavras | 4 páginas
  • Direito egipcio
    1961 palavras | 8 páginas
  • Pesquisa de Marketing - Briefing
    2715 palavras | 11 páginas
  • Metodos sondagem solo
    2878 palavras | 12 páginas
  • Padronização
    3902 palavras | 16 páginas
  • SISTEMA DE INFORMA ES GERENCIAIS
    3350 palavras | 14 páginas
  • pesquisa de marketing senac
    3815 palavras | 16 páginas
  • direto tributario
    5367 palavras | 22 páginas
  • História
    12080 palavras | 49 páginas
  • Erros encontrados na administração publica no brasil
    12771 palavras | 52 páginas