Baixe o app para aproveitar ainda mais
Prévia do material em texto
Algoritmos e Estruturas de Dados I Complexidade Assintótica Notação Assintótica Classes de Complexidade 2015/1 Conteúdo Relembrando Análise de complexidade de algoritmos Melhor caso, pior caso, caso médio Complexidade assintótica Notação assintótica Classes de complexidade Um problema intratável Análise de Algoritmos Analisar um algoritmo é estimar os recursos que ele necessita para sua execução em termos de Tempo de execução é proporcional ao número de comandos ou operações relevantes executadas calculado a partir do número de instruções executado para um algoritmo com uma dada entrada de dados Espaço em memória quantidade de memória requerida medido também em relação ao tamanho da entrada Complexidade de tempo o número de passos executados por um algoritmo é uma medida da complexidade de tempo do algoritmo O número de passos executados depende do tamanho da entrada e pode depender também do arranjo específico dos dados na entrada, isto é, de como os dados estão combinados entre si para uma entrada de mesmo tamanho Definição de casos de complexidade Para uma mesma entrada de tamanho n podemos identificar os seguintes casos quanto ao número de instruções e, consequentemente, o tempo de execução: melhor caso menor tempo de execução sobre todas as entradas de tamanho n é a entrada para a qual o algoritmo executa menos comandos, ou seja, é mais rápido, comparando com todas as entradas de tamanho n pior caso maior tempo de execução sobre todas as entradas de tamanho n é a entrada para a qual o algoritmo executa mais passos, isto é, demora mais, comparado com todas as entradas de tamanho n caso médio ou esperado corresponde à média dos tempos de execução para TODAS as entradas de tamanho n Importância dos casos Pior caso muitas vezes é considerada a medida mais importante fornece um limite superior para o número de passos que o algoritmo pode efetuar, para qualquer entrada de tamanho n Caso médio é o caso esperado é uma medida da maioria dos casos considerada muito importante a análise do caso médio pode ser complexa Melhor caso uso menos freqüente, para situações específicas Exemplos Pesquisa com sucesso em vetor não ordenado Melhor caso: 1 Pior caso: n Caso médio: (n+1)/2 Quicksort Melhor caso: n log n Pior caso: n2 Caso médio: n log n Observem que o caso médio não é a média entre o melhor e o pior caso Técnicas de Análise de Algoritmos a análise de algoritmos utiliza técnicas de matemática discreta: manipulação de somas e produtos contagem e enumeração dos elementos de um conjunto permutações fatoriais e coeficientes binomiais solução de equações de recorrência determinar o tempo de execução de um programa pode ser uma tarefa matematicamente complexa determinar a ordem do tempo de execução pode ser uma tarefa mais simples neste caso, não estamos preocupados em determinar de forma exata a função de complexidade Comportamento Assintótico das funções de custo o custo de um algoritmo é função do tamanho n do problema o custo aumenta quando n aumenta para valores pequenos de n qualquer algoritmo custa pouco para ser executado inclusive os algoritmos ineficientes para problemas de tamanho pequeno a escolha do algoritmo não é um problema crítico logo, a análise de algoritmos é importante para valores grandes de n assim, é importante considerar o comportamento das funções de custo para valores grandes de n Comportamento Assintótico Comportamento assintótico das funções de custo representa o comportamento das funções para n grande, isto é, o limite de f(n) quando n cresce quando o tamanho da entrada é muito grande, apenas a ordem de crescimento das funções de custo é relevante eficiência assintótica Análise assintótica como o algoritmo se comporta quando o tamanho do problema é muito grande? Tempo de execução Espaço em memória Notação Assintótica Para expressar o comportamento assintótico de uma função de custo utilizamos algumas notações: Notação O (O grande - Big Oh) Limite assintótico superior Notação Θ (Theta) Limite assintótico justo (restrito, firme) Notação Ω (Omega) Limite assintótico inferior Limite superior - Notação O Definição: uma função f(n) é O(g(n)) se existem duas constantes c, n 0 >= 0 tais que 0 f(n) c·g(n) para todo n n 0 significado: c·g(n) é um limite superior de f(n) para valores grandes de n f(n) = O(g(n)) dizemos que g(n) domina assintoticamente f(n) Análise de algoritmos: Notação O Exemplo 1 f(n) = 3n2+2n+1 é O(n2) 3n2+2n+1 c.n2 dividindo ambos os lados por n2 3 + 2/n + 1/n2 c verdadeiro para n 0 = 1 e c = 6 Exemplo 2 f(n) = 2n é O(n2) 2n c.n2 dividindo ambos os lados por n2 2/n c verdadeiro para n 0 = 1 e c = 2 Análise de algoritmos: Notação O Exemplo 3 f(n) = 2n é O(n) 2n cn dividindo ambos os lados por n 2 c verdadeiro para n 0 = 0 e c = 2 Exemplo 4 f(n) = 1000n3 é O(n10) 1000n3 cn10 verdadeiro para n 0 = 3 e c = 1 Análise de algoritmos: Notação O Exemplo 5 Seja g(n) = n e f(n) = n2 f(n) domina g(n) assintoticamente? Ou seja, g(n) = O(f(n)) ? Para responder: encontrar 2 constantes positivas c e n 0 tais que g(n) c·f(n) para todo n n 0 Fazendo c = 1 e n 0 = 0 => g(n) é O ( f(n) ) Exemplo 6 Seja g(n) = n e f(n) = n2 g(n) domina assintoticamente f(n)? f(n) é O(g(n))? Não... Análise de algoritmos: Notação O Notação O: indica um limite superior para a ordem de crescimento da função de custo Considerações constantes aditivas e multiplicativas não são importantes: podem ser desprezadas um polinômio de grau k é O(nk) o termo de maior ordem da função é que conta isto é análise assintótica à medida que a entrada cresce, o termo de maior ordem domina a função de custo Análise de algoritmos: Notação O Notação O Expressa o limite superior do custo: upper bound Mais exemplos f(n) = 3n3 + 2n2 + n+1 é O(n3) f(n) = 7n2 é O(n4) f(n) = 8n3 + 5 log n + 2 é O(n3) f(n) = 2log2 n + log n + 3 é O(log2 n) F(n) = 5.2n + 5n10 é O(2n) Notação O: perguntas O problema de encontrar o maior elemento de um conjunto de n elementos é O(n)? é O(n3)? é O(log n)? é O(2n)? Para resolver um problema P são conhecidos dois algoritmos Algoritmo A com custo 100n Algoritmo B com custo 2 n2 Qual é o melhor algoritmo? Notação Assintótica Para expressar o comportamento assintótico de uma função de custo utilizamos algumas notações que indicam a taxa de crescimento do tempo de execução quando o tamanho da entrada cresce Notação O (O grande - Big Oh) Limite assintótico superior Notação Θ (Theta) Limite assintótico justo (restrito, firme) Notação Ω (Omega) Limite assintótico inferior Notação Omega - limite inferior Uma função f(n) é (g(n)) se existem constantes positivas c, n 0 tais que f(n) c·g(n) para n n 0 Significado c·g(n) é um limite inferior de f(n) para n grande lower bound Exemplo f(n) = n2 é (n) basta fazer c = 1 e n0 = 1 Notação Theta - limite estrito, justo, firme Uma função f(n) é (g(n))se é O(g(n)) e (g(n)), isto é: se existem constantes c 1 , c 2 , n 0 > 0 tais que 0 c1 g(n) f(n) c2g(n) para todo nn 0 Significado f(n) e g(n) tem a mesma ordem de crescimento indica um limite firme tight bound Notação Theta – limite firme Exemplo: mostrar que f(n) = 2n+1 é (n) Encontrar constantes c 1 , c 2 , n 0 > 0 tais que 0 c1 n 2n + 1 c2n para todo nn0 primeira parte da equação: c1 n 2n + 1 verdadeiro para c1 = 1 e n0 = 1 segunda parte da equação: 2n + 1 c2n verdadeiro para c2 = 3 e n0 = 1 Portanto, 2n+1 = (n) Limites assintóticos justo superior inferior Outras notações assintóticas: o e mais duas notações complementares: o minúsculo e Uma função f(n) é o(g(n)) se, para qualquer constante c > 0 existe uma constante n 0 > 0 tal que f(n) < c g(n) n n 0 exemplo: 2n = o(n2) para n 0 = 1 exemplo: 2n2 = O(n2) mas 2n2 ≠ o(n2) Outras notações assintóticas: o e mais duas notações complementares: o minúsculo e Uma função f(n) é (g(n)) se, para qualquer constante c > 0 existe uma constante n 0 > 0 tal que c g(n) < f(n) n n 0 exemplo: n2/2 = (n) para n 0 = 1 exemplo: n2/2 = (n2) mas n2/2 ≠(n2) Propriedades e características ● O, , são transitivas e reflexivas ● f(n) = O(g(n)) e g(n) = O(h(n)) então f(n) = O(h(n)) ● f(n) = O(f(n)) ● é simétrica ● f(n) = (g(n)) sse g(n) = (f(n)) ● f(n) = O(g(n)) sse g(n) = (f(n)) ● analogia com 2 números reais a e b f(n) = O(g(n)) a b f(n) = o(g(n)) a < b f(n) = (g(n)) a b f(n) = (g(n)) a > b f(n) = (g(n)) a = b Operações com a Notação O Sejam f, g funções reais positivas e k uma constante Então, temos: f(n) = O(f(n)) O(f(n)) + O(f(n)) = O(f(n)) O(O(f(n))) = O(f(n)) O(k.f(n)) = k.O(f(n)) = O(f(n)) O(f(n) + g(n)) = O(g(n)) + O(f(n)) O(g(n)) + O(f(n)) = O(max(f(n), g(n))) O(g(n)) * O(f(n)) = O(f(n) * g(n)) f(n)*O(g(n)) = O(f(n) * g(n)) Notação assintótica em equações notação assintótica em fórmulas: como interpretar exemplo: significado: a notação está substituindo uma função que não é importante definir precisamente é equivalente a: em que f(n) = θ (n), por exemplo, f(n) = 4n + 5 Notação assintótica em equações Atenção quanto ao uso da notação O e outras notações que envolvem quantidades não precisas => o sinal de igualdade é unidirecional a igualdade significa "pertence" ou "está contido" Exemplo: Válido: n = O(n2) Inválido: O(n2) = n Assim: nunca devemos escrever uma igualdade onde a notação O aparece sozinha do lado esquerdo se não poderíamos concluir um absurdo tal como n2 = n Crescimento das funções de custo 0 1000 2000 3000 4000 5000 1 3 5 7 9 11 13 15 17 19 f(n) = n f(n) = log(n) f(n) = n log(n) f(n) = n 2^ f(n) = n 3^ f(n) = 2 n^ Classes de Complexidade Classificação dos problemas segundo seu comportamento assintótico especificado pela notação O complexidade constante: f(n) é O(1) complexidade logarítmica: f(n) é O(log n) complexidade linear: f(n) é O(n) complexidade linear logarítmica: f(n) é O(nlog n) complexidade quadrática: f(n) é O(n2) complexidade cúbica: f(n) é O(n3) complexidade exponencial: f(n) é O(2n) Análise de complexidade A análise de complexidade dos algoritmos revela a importância de encontrar algoritmos com a menor taxa de crescimento possível para a resolução dos problemas Em última análise a taxa de crescimento dos algoritmos determina qual é o maior problema que pode ser resolvido por um computador A análise de complexidade também classifica os problemas em tratáveis e intratáveis Algoritmos exponenciais x polinomiais algoritmo com tempo de execução exponencial: O(2n) ou superior algoritmo com tempo de execução polinomial: O(p(n)) onde p(n) é um polinômio o tempo de execução destas duas classes é muito distinto quando n cresce algoritmos exponenciais estão relacionados a algoritmos de pesquisa exaustiva solução por força bruta problemas intratáveis algoritmos polinomiais: resultado de uma boa solução para o problema Um problema é considerado tratável: se existe um algoritmo de classe polinomial ou inferior para resolvê-lo intratável: se existe um algoritmo para resolvê-lo cuja classe é exponencial ou superior Exemplo de um problema intratável O problema do caixeiro viajante Um caixeiro viajante deseja visitar n cidades de tal forma que sua viagem inicie e termine em uma mesma cidade e cada cidade é visitada apenas uma vez; supondo que exista sempre um caminho entre duas cidades quaisquer, o problema é encontrar a menor rota que o caixeiro viajante pode utilizar na sua viagem Qual é o custo para encontrar a menor rota? Problema do caixeiro viajante Para 4 cidades C1 C2 C3 C4 8 8 9 5 3 4 Solução: enumerar as rotas; calcular a distância para cada rota; escolher a menor Problema do caixeiro viajante Para 4 cidades C1 C2 C3 C4 Rotas possíveis C1 C2 C3 C4 C1 = 25 C1 C2 C4 C3 C1 = 24 C1 C3 C2 C4 C1 = 25 C1 C3 C4 C2 C1 = 24 C1 C4 C2 C3 C1 = 25 C1 C4 C3 C2 C1 = 25 8 8 9 5 3 4 Solução: enumerar as rotas; calcular a distância para cada rota; escolher a menor Problema do caixeiro viajante Para 4 cidades número de rotas = 6 número de adições por rota C1C3 + C3C4 + C4C2 + C2C1 : 3 adições número total de adições 6*3 = 18 Para n cidades número de rotas = (n-1)! número de adições = n -1 Número total de adições = (n-1)! * (n -1) = n! – (n-1)! Para n = 50 => número de adições = ? Calcular o tempo é necessário para obter a solução do problema Problema do caixeiro viajante Para 4 cidades número de rotas = 6 número de adições por rota C1C3 + C3C4 + C4C2 + C2C1 : 3 adições número total de adições 6*3 = 18 Para n cidades número de rotas = (n-1)! número de adições = n -1 Número total de adições = (n-1)! * (n -1) = n! – (n-1)! Para n = 50 número de adições = 1064 Quanto tempo é necessário apenas para executar as adições? Em um computador que faz 109 adições por segundo => 1045 séculos apenas para calcular as rotas Bibliografia Knuth, volume 1 págs 94-107 Cormen, Leiserson, Rivest, Stein Algoritmos: teoria e prática - 2ª. Edição – tradução Cap1: págs 3 a10 Cap2: págs 11 a 20 Cap3: págs 32 a 40 Nivio Ziviani Projeto de Algoritmos, segunda edição Cap. 1 Complexidade Assintótica Notação Assintótica Classes de Complexidade Conteúdo Análise de Algoritmos Complexidade de tempo Slide 5 Importância dos casos Exemplos Slide 8 Comportamento Assintótico das funções de custo Comportamento Assintótico Notação Assintótica Limite superior - Notação O Análise de algoritmos: Notação O Slide 14 Slide 15 Slide 16 Slide 17 Notação O: perguntas Slide 19 Notação Omega - limite inferior Notação Theta - limite justo Slide 22 Limites assintóticos Outras notações assintóticas Slide 25 Propriedades e características Slide 27 Slide 28 Slide 29 Slide 30 Classes de Complexidade Análise de complexidade Algoritmos exponenciais x polinomiais Exemplo de um problemaintratável Problema do caixeiro viajante Slide 36 Slide 37 Slide 38 Bibliografia
Compartilhar