View
104
Download
0
Category
Preview:
Citation preview
ICC2 Aula 7
Fábio Nakano
Crescimento de funções
Tempo de execução
Impacto da melhoria do hardware
O que tem essas funções com o tempo de execução?
Comparando taxas de crescimento
Algoritmos, operações e complexidade
• Quanto tempo leva uma atribuição?• Quanto tempo leva uma comparação?
Acesso sequencial/Busca linear
Qual é a função dominante?
polinomiais
• Bubble sort é n^2• O caso médio do simplex (LP) é n^3
• Qual é o termo dominante da função:
• f(n)=n^5+200*n^4+5000n^3+20000n^2 ??
Busca binária
Mergesort/heapsort/quicksort
• n*log(n)
• Como compara com o bubblesort?
Problema da mochila• Vamos viajar mas cada um só pode levar uma mala
com o que couber.
• Como tudo é igualmente necessário, queremos maximizar o número de itens.
• Tem que verificar todas as combinações possíveis... Quantas são?
• Idéia do conjunto das partes (necessário para MD e ITC)
Combinações de algoritmos e combinações de funções
• Buscar num vetor desordenado– Busca linear– Ordenar e buscar
• Ordenações por diversos parâmetros• E se tiver vários parâmetros?– Busca direta– Ordena a cada vez que busca– Array de índices
Exercitemos... Qual cresce mais rápido, se uma “descola” da outra e se
somarmos uma a outra e se multiplicarmos?• Constantes
• Logs• Linear• Polinomial• Misto log-pol• Exponencial• (escolher funcoes e fazer na classe)
Podemos agrupar as funções em conjuntos?
Notação assintótica e propriedades
• Aula 4 do Delano• (fazer a conexão entre os exemplos e as
propriedades)
Definições, teoremas e algoritmos
• Definição é uma especificação precisa de um objeto.
• Um teorema é uma especificação precisa de um procedimento (que geralmente constrói um objeto a partir do outro para provar que uma afirmação é verdadeira)
• Um algoritmo é uma especificação precisa de um procedimento.
Exemplos
• Definição: n!=n*(n-1)!• Construa um método que calcula n!• Construa um método que calcula a soma dos n
primeiros inteiros• Teorema 1: A soma dos n primeiros inteiros é
n(n+1)/2• Construa um método que calcula a soma dos n
primeiros inteiros usando o Teorema 1• Compare as complexidades.
Indução matemática
• Prove por indução que n^2>2n+1 para n>2• Prove por indução que 2^n > n^2
• Base• Hipótese• Passo
Recommended