Analise de Eficiencia e Notacao de Ordem para Codigos de Alta Performance

1 Análise de Eficiência Notação Ordem de Códigos de Alta Performance PROFa PATRÍCIA MAGNA profpatriciamagnafiapcombr Códigos de Alta Perfomance Profa Patrícia Magna 2 Eficiência de um Algoritmo Existem 2 aspectos de eficiência considerados tempo requerido e espaço de armazenamento Geralmente o programador deverá otimizar um aspecto às custas do outro Quantidade de Memória Utilizada Tempo de Execução do Programa Códigos de Alta Perfomance Profa Patrícia Magna Códigos de Alta Perfomance Profa Patrícia Magna 3 Como analisar Eficiência de um Algoritmo A medida de tempo seria dada pelo número de operações críticas ou essenciais que são efetuadas durante a execução do algoritmo a fim de resolver um específico problema por exemplo a busca de um registro em um arquivo O tamanho do arquivo no qual o algoritmo atua sempre é referenciado em relação à quantidade n de registros que o compõe Códigos de Alta Perfomance Profa Patrícia Magna 4 Quais são as operações críticas São as operações essenciais que deve ser realizadas para resolução do aplicação Exemplos de operações críticas Para algoritmos de busca seriam apenas as comparações sobre chaves Para algoritmos de soma de elementos de vetores seriam apenas as adições sobre os elementos dos vetores Para algoritmos de ordenação seriam as comparações sobre chaves e movimentação de registros ou trocas etc Códigos de Alta Perfomance Profa Patrícia Magna 5 Como analisar Eficiência de um Algoritmo A análise pode ser basear na identificação das seguintes situações Melhor caso Caso médio Pior caso Códigos de Alta Perfomance Profa Patrícia Magna 6 Exemplo de como analisar Eficiência de um Algoritmo Nos métodos de busca sequencial supondo um arquivo com 8 registros Melhor caso chave ser 1º registro 1 comparação Caso médio chave estar na 4ª posição do arquivo 5 comparações Pior caso chave ser do 8º registro do arquivo 8 comparações Mas Como descrever de de forma mais geral o comportamento de um algoritmo em relação a quantidade de dados a serem manipulado 7 Descrevendo o comportamento da eficiência dos Métodos de Busca Sequencial e Busca Binária Função que melhor descreve o número de comparações medidos na execução Foi usado como log n log2 n Códigos de Alta Perfomance Profa Patrícia Magna 8 Como analisar a Eficiência de um Algoritmo No caso dos métodos de busca encontrar uma função que descreva o comportamento do método em relação ao número de registros foi simples Podem ser encontradas funções bem diferentes fazendo as medidas de número de operações críticas em relação ao número de dados Suponha que 2 métodos diferentes que executam a mesma tarefa chegase às seguintes funções Qual dos métodos é o mais eficiente fmetodo1n 001n2 10n fmetodo2n 10 n n log n Códigos de Alta Perfomance Profa Patrícia Magna 9 Comparando de Forma Numérica as Funções 0 10000 20000 30000 40000 50000 60000 70000 80000 90000 100000 110000 0 20000000 40000000 60000000 80000000 100000000 120000000 001 n2 10n 10 n n log n É mais eficiente por exigir menos comparações quando a quantidade de dados aumenta Códigos de Alta Perfomance Profa Patrícia Magna 10 Como analisar a Eficiência de um Algoritmo Analisando o comportamento das funções observamos que para valores de n grandes a função do método 1 supera e muito o número de operações críticas em relação ao 2º método Mas deve haver uma forma mais fácil de descobrir o comportamento da variação das operações críticas sem ter que construir gráficos Será fmetodo1n 001n2 10n fmetodo2n 10 n n log n Sim existe e para isso existe uma notação conhecida como da ordem de ou big O O Códigos de Alta Perfomance Profa Patrícia Magna 11 Iniciando com a Notação da Ordem de O Suponha a seguinte função 001n2 10n n A001 n2 B 10 n AB AB n2 10 1 100 101 101 50 25 500 525 021 100 100 1000 1100 011 500 2500 5000 7500 003 1000 10000 10000 20000 002 5000 250000 50000 300000 001 10000 1000000 100000 1100000 001 50000 25000000 500000 25500000 001 100000 100000000 1000000 101000000 001 Códigos de Alta Perfomance Profa Patrícia Magna 12 Notação da Ordem de O No exemplo anterior quando n tornase grande a função fica apenas proporcional a n2 Dizse que de 001n2 10n é da ordem da função n2 Utilizase a seguinte notação para representar essa proporcionalidade On2 Dizse da ordem de n2 Essa notação é muito utilizada para analisar com que proporção varia o tempo ou número de operações críticas são efetuadas e desta forma ter de alguma forma ideia da eficiência do algoritmo utilizado Códigos de Alta Perfomance Profa Patrícia Magna 13 Propriedade Assintótica Se fn for Ogn ocasionalmente n b tornarseá permanentemente menor ou igual a algum múltiplo de gn Isto significa que fn está limitada por gn de cima para baixo ou que fn é uma função menor que gn Outro modo mais formal é dizer que fn é assintoticamente limitada por gn Traduzindo A função gn para valores altos de n sempre vai resultar um valor maior do que fn Desta forma fn sempre será limitada pela função gn 14 Descrevendo o comportamento dos Métodos de Busca On Olog n Códigos de Alta Perfomance Profa Patrícia Magna 15 Notação da Ordem de O Funções que são usadas para descrever o comportamento dos algoritmos são Oconstante Olog n On On log n On2 Onk O2n As funções já estão apresentadas de forma hierárquica conforme será demonstrado nos próximos slides Códigos de Alta Perfomance Profa Patrícia Magna 16 Comparação entre as funções c1 e log n 0 05 1 15 2 25 0 10 20 30 40 50 60 70 80 90 100 110 n funções c log n Códigos de Alta Perfomance Profa Patrícia Magna 17 Comparação entre log n n log n e n 0 10 20 30 40 50 60 70 80 90 0 10 20 30 40 50 60 n funções log n n log n n Códigos de Alta Perfomance Profa Patrícia Magna 18 Comparação entre n log n n2log n e n2 0 500 1000 1500 2000 2500 3000 3500 4000 4500 0 10 20 30 40 50 60 n funções n log n n2 n2 log n Códigos de Alta Perfomance Profa Patrícia Magna 19 Comparação entre as funções n2 log n e n3 0 20000 40000 60000 80000 100000 120000 140000 1 2 3 4 5 10 20 30 40 n funções n3 n2 log n Códigos de Alta Perfomance Profa Patrícia Magna 20 Notação da Ordem de O Funções que são usadas para descrever o comportamento dos algoritmos Oconstante Olog n busca binária On busca sequencial On log n O n2 Onk complexidade polinomial problemas P NP e NP completo O2n algoritmos conhecidos como intratáveis métodos de ordenação Códigos de Alta Perfomance Profa Patrícia Magna 21 Eficiência de Algoritmos de Ordenação Através do conceito de ordem de podese analisar a ordem de um algoritmo e categorizálo como eficiente ou ineficiente Vamos a partir de agora descrever a eficiência de algoritmos e métodos usando essa notação da ordem de partiuAlgoritmoOrdenação REFERÊNCIAS ASCÊNCIO AFG ARAUJO GS Estruturas de Dados Algoritmos Análise de Complexidade e Implementações em JAVA e CC São Paulo EdPearson Prentice Hall 2010 PEREIRA SL Estruturas de Dados Fundamentais Conceitos e Aplicações São Paulo Ed Érica 1996 TENEMBAUM AM et al Estruturas de Dados usando C Makron Books Ltda 1995 ZIVIANI Nivio Projeto de algoritmos com implementações em Pascal e C São Paulo Pioneira 2000 23 Copyright 2024 Profa Patrícia Magna Todos direitos reservados Reprodução ou divulgação total ou parcial deste documento é expressamente proibido sem o consentimento formal por escrito dos professores Códigos de Alta Perfomance Profa Patrícia Magna