Análise e Complexidade de Algoritmos

José Carlos ToniazzoCiência da Computação

Roteiro

Introdução; Algoritmos; Como Escolher o Melhor; Complexidade de Algoritmos; Tempo de Execução; Análise Assintótica; Notações; O que precisamos...

Introdução Em Ciência da Computação, a análise de algoritmos tem

como função determinar os recursos necessários para executar um dado Algoritmo. A maior parte dos algoritmos são pensados para trabalhar com entradas (inputs) de tamanho arbitrário. Em geral, a eficiência ou complexidade de um algoritmo é função do tamanho do problema, do número de passos necessário (complexidade temporal) e da complexidade espacial ou de memória do sistema usado para executar o algoritmo.

Esta disciplina faz parte da mais vasta teoria da complexidade computacional, que permite fazer estimativas quanto aos recursos necessários para que um algoritmo resolva um determinado problema computacional.

Introdução Assim, o objetivo final não é apenas fazer códigos que

funcionem, mas que sejam também eficientes. Para isso, deve-se estudar alguns tipos de problemas que podem ser resolvidos computacionalmente. Em seguida, deve ser visto como a abordagem adotada para resolver pode influenciar, levando a um algoritmo mais ou menos eficiente.

"Ao verificar que um dado programa está muito lento, uma pessoa prática pede uma máquina mais rápida ao seu chefe. Mas o ganho potencial que uma máquina mais rápida pode proporcionar é tipicamente limitado por um fator de 10, por razões técnicas ou econômicas. Para obter um ganho maior, é preciso buscar melhores algoritmos. Um bom algoritmo, mesmo rodando em uma máquina lenta, sempre acaba derrotando (para instâncias grandes do problema) um algoritmo ruim rodando em uma máquina rápida. Sempre."

Algoritmo

Seqüência de instruções necessárias para a resolução de um problema bem formulado;

Permite implementação computacional;

Legal,isso É MOLEZA!

Como Escolher um Algoritmo?

Tempo de processamento... Um algoritmo que realiza uma tarefa em 10

horas é melhor que outro que realiza em 10 dias

Quantidade de memória necessária... Um algoritmo que usa 1MB de memória RAM

é melhor que outro que usa 1GB

Complexidade de Algoritmos

Um algoritmo resolve o problema quando para qualquer entrada produz uma resposta correta;

Mesmo resolvendo um problema, um algoritmo pode não ser aceitável na prática por requerer muito espaço e tempo;

Um problema é considerado INTRATÁVEL, se não existe um algoritmo para ele cuja demanda de recursos computacionais seja razoável.

Questões a Fazer Sobre a Complexidade O problema em questão é tratável?

Existe um algoritmo que demande quantidade razoável de recursos computacionais?

Quais os custos deste algoritmo?

Existe um algoritmo melhor?

Como comparar algoritmos?

Sendo Assim...

Estas e outras questões são abordadas em uma área de conhecimento denominada:

Análise de complexidade de algoritmos

O que Analisar em um Algortimo

O custo final de um algoritmo pode estar relacionado a diversos fatores: - Tempo de execução - Utilização de memória principal - Utilização de disco - Consumo de energia, etc...

• Medidas importantes em outros contextos: - legibilidade do código - custo de implementação - portabilidade - extensibilidade

Pensando Bem Medir o tempo gasto por um algoritmo

Não é uma boa opção Depende do compilador Pode preferir algumas construções ou otimizar melhor Depende do hardware GPU vs. CPU, desktop vs. smartphone

Estudar o número de vezes que operações são executadas... Hummmm! Parece Razoável!

Um Exemplo

Exemplo: Solução de um sistema de equações lineares AX = 0

Métodos: Cramer (determinantes) Gauss (escalonamento)

O que Temos Estimativa empírica de tempo, para um processador rodando em 3GHz:

n Cramer Gauss 2 4 ns 2 ns 3 12 ns 8 ns 4 48 ns 20 ns 5 240ns 40 ns 10 7.3ms 330 ns 20 152 anos 2.7 ms

Na maioria dos casos, complexidade em tempo é preocupação principal. Mas a resposta pode ser imprecisa...

Outro Exemplo Busca seqüencial

Dado um vetor de números, verificar se um número chave encontra-se neste vetor

char achou = 0;i = 0;

while (!achou && i<n) achou = (vet[i] == chave);i++;

if (achou) return(i);else return(1);

Outro Exemplo Busca seqüencial

Neste caso não existe um número fixo de operações!

Isto vai depender de onde o valor chave é encontrado

Por isso, é comum realizar a contagem para: O melhor caso O pior caso E o caso médio

Tempo de Execução Um algoritmo pode rodar mais rápido para

certos conjunto de dados do que para outros;

Encontrar um caso médio pode ser muito difícil, assim os algoritmos são geralmente medidos pela complexidade de tempo do pior caso.

Tempo de Execução Além disso, para certas áreas de aplicação (controle

de tráfego aérea, cirurgias, etc.), o conhecimento da complexidade do pior caso é crucial.

O que Analisar Então?

Análise de Complexidade de tempo Análise Experimental Análise Teórica

Complexidade De Tempo Pode ser medida empiricamente:

Com funções para o cálculo do tempo. Exemplo:

#include <time.h>time_t t1,t2;time(&t1);/*Operações*/time(&t2);double diferenca = difftime(t2,t1);//diferença em segundos

Estudo Experimental

escreva um programa que implemente o algoritmo;

execute o programa com conjuntos de dados de vários tamanhos e composições;

use um método para medir o tempo de execução com exatidão;

Estudo Experimental Estudos experimentais possuem várias limitações:

é preciso implementar e testar o algoritmo para determinar seu tempo de execução;

os experimentos só podem ser feito para um conjunto limitado de dados de entrada, assim os tempos de computação resultantes podem não ser indicativos dos tempos de execução para entradas não incluídas no experimento;

para comparar dois algoritmos, devem ser utilizados o mesmo ambiente de hardware e software.

Análise Teórica iremos agora apresenta um metodologia geral para analisar o

tempo de computação de algoritmos que utiliza a descrição de algoritmos em alto-nível ao invés de testar uma de suas implementações;

leva em consideração todas as possíveis entradas;

permite avaliar a eficiência de qualquer algoritmo de uma maneira que é independente dos ambientes de hardware e software.

Análise Teórica: analisar os passos necessários de um algoritmo e seu custo

Análise Assintótica PROCEDIMENTO

1) Escreve o algoritmo em pseudo-código;

2)Conta operações primitivas (computações de baixo nível que podem ser consideras em tempo constante de execução, como testes,

atribuições, laços...);

3) Análise a complexidade do algoritmo usando a notação Big-Oh.

Análise Assintótica Para valores suficientemente pequenos de n,

qualquer algoritmo custa pouco para ser executado, mesmo os ineficientes;

Logo, analisamos algoritmos para grandes valores de n ;

Estudamos o comportamento assintótico das funções de complexidade de um programa

(comportamento pra grandes valores de n)

Algumas Notações Notações que usaremos na análise de algoritmos:

f(n) = O(g(n)) (lê-se big-oh, big-o ou “da ordem de”) se existirem constantes c e n0 tal que f(n) ≤ c*g(n) quando n ≥ n0

A taxa de crescimento de f(n) é menor ou igual à taxa de g(n)

f(n) = Ω(g(n)) (lê-se “ômega”) se existirem constantes c e n0 tal que f(n) ≥ c*g(n) quando n ≥ n0

A taxa de crescimento de f(n) é maior ou igual à taxa de g(n)

Algumas Notações

Notações que usaremos na análise de algoritmos:

f(n) = Θ(g(n)) (lê-se “theta”) se e somente se f(n) = O(g(n)) e f(n) = Ω(g(n))

-A taxa de crescimento de f(n) é igual à taxa de g(n)

Um Pequeno Exercício Algoritmo 1: f1(n) = 2n2 + 5n = O(n2)

Algoritmo 2: f2(n) = 500n + 4000 = O(n)

Um polinômio de grau d é de ordem O(nd). Como uma constante pode ser considerada como um polinômio de grau 0, então dizemos que uma constante é O(n0) ou seja O(1).

Qual algoritmo demanda maior tempo de execução?

Revisão de Matemática

Logaritmos; Expoentes; Somatório; Progressão Geométrica; Progressão Aritmética; Ceiling e Floor

Porque Matemática? Determinar o tempo de execução de um algoritmo pode ser complexo;

Determinar a complexidade assintótica, sem preocupação com as constantes envolvidas, pode ser uma tarefa mais simples;

Análise de algoritmos utiliza técnicas de matemática discreta:

Manipulação de somas, produtos, permutações, coeficientes binomiais, equações de recorrência

E Porque Estudar ACA? Por que analisar a complexidade dos algoritmos?

A preocupação com a complexidade de algoritmos éfundamental para projetar algoritmos eficientes;

Podemos desenvolver um algoritmo e depois analisar a sua complexidade para verificar a sua eficiência;

Mas o melhor ainda é ter a preocupação de projetaralgoritmos eficientes desde a sua concepção.

Isso é Ciência da Computação!

Obrigado Pela Atenção! O caminho da disciplina foi apresentado. Não é

trivial;

Temos que ter comprometimento, pois a disciplina exige atenção;

Conto com a colaboração dos colegas para termos um bom semestre;

Até a próxima!

Referências

http://wiki.icmc.usp.br/images/d/de/Analise_complexidade.pdf

http://homepages.dcc.ufmg.br/~cunha/teaching/20121/aeds2/complexity.pdf

http://www.ime.usp.br/~song/mac5710/slides/01complex.pdf