ALGORITMOS AVANÇADOS UNIDADE I Análise de Algoritmo ...luizleao.com/Docencia/FAP/ALGAVANC/ALGORITMO_AVANC_UND_01.pdf · –É um problema base para o projeto de microchips, sequenciamento

ALGORITMOS AVANÇADOS

Luiz Leão – [email protected]

http://www.luizleao.com

UNIDADE I – Análise de Algoritmo - Notação O

mailto:[email protected]

http://www.luizleao.com/



Conteúdo Programático

• 1.1 - Algoritmo

• 1.2 - Estrutura de Dados

• 1.2.1 - Revisão de Programas em C++ envolvendo Vetores,

Matrizes, Ponteiros, Registros (Struct) e Funções.

• 1.3 - O que é Analise de Algoritmos

• 1.4 - Sobre o Elemento da Análise Assintótica - Notação O

• 1.4.1 - Notação O

• 1.4.2 - Sobre a função

• 1.4.3 - Operações com a Notação O



• Algoritmo é uma sequência finita de instruções bem

definidas e não ambíguas, cada uma das quais

devendo ser executadas mecânica ou

eletronicamente em um intervalo de tempo finito e

com uma quantidade de esforço finita.

Algoritmo



• É um modo particular de armazenamento e organização de

dados em um computador de modo que possam ser usados

eficientemente

Estrutura de Dados



• Estrutura Condicional

• Estrutura de Repetição

• Vetores

• Matrizes

Revisão Programação



• A análise de algoritmos estuda a correção e o

desempenho de algoritmos.

• Em outras palavras, a análise de algoritmos

procura respostas para perguntas do seguinte

tipo:

– Este algoritmo resolve o meu problema?

– Quanto tempo o algoritmo consome para processar uma 'entrada' de tamanho n?

Analise de 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 projetar

algoritmos eficientes desde a sua concepção.

Por que analisar a complexidade dos algoritmos?



• Além disso, a análise de algoritmos estuda certos paradigmas

(como divisão-e-conquista, programação dinâmica, gula,

busca local, aproximação, etc.) que se mostraram úteis na

criação de algoritmos para vários problemas computacionais.

• A análise de algoritmos foi inventada e difundida por D.E.

Knuth (veja a série de livros The Art of Computer

Programming). Knuth foi o pai da ideia de prever o tempo de

execução e o consumo de espaço de um algoritmo.




• Um algoritmo serve para resolver um determinado

problema, e todos os problemas têm sempre uma

entrada de dados

• O tamanho dessa entrada (n) tem geralmente efeito

direto no tempo de resposta de um algoritmo




• Dependendo do problema a ser resolvido, já existem

algoritmos prontos ou que podem ser adaptados

• O problema é: Qual algoritmo escolher?

Analise de Algoritmos (Cont.)



• Tomemos duas soluções para localizar um elemento em um

vetor: LIN e BIN

• Temos dois computadores diferentes, A e B, sendo A um

Core 2 Duo e B um Celeron.

• Qual é a melhor solução? LIN ou BIN ?

Como Comparar Duas Soluções Para Um Mesmo

Problema ?



Como Comparar Duas Soluções Para Um Mesmo

Problema ?



• Para valores suficientemente pequenos de n,

qualquer algoritmo custa pouco para ser executado,

mesmo os algoritmos ineficientes;

• A Análise Assintótica é a análise de algoritmos quando realizada para valores grandes de n

considerando-se o devido custo computacional das

funções do programa;

Análise Assintótica



Tipos de Complexidade

• Espacial:

– Este tipo de complexidade representa, por exemplo, o

espaço de memória usado para executar o algoritmo.

• Temporal:

– Este tipo de complexidade é o mais usado podendo

– Dividir-se em dois grupos:

• Tempo (real) necessário à execução do

algoritmo (como podemos medir?)

• Número de instruções necessárias à execução.



Tipos de Complexidade

• Em ambos os casos, a complexidade é medida de acordo com o tamanho dos dados de entrada (n)

• Estamos mais interessados em calcular a

Complexidade Temporal de um algoritmo!



Complexidade de Algoritmos

• Existem três perspectivas para análise de

complexidade: – Melhor Caso

– Caso Médio

– Pior Caso

• Nas três perspectivas, a função f(n) retorna a

complexidade de um algoritmo com entrada de tamanho n



Análise do Melhor Caso

• Definido pela letra grega Ω (Ômega).

• Exprime o menor tempo de execução de um algoritmo para uma entrada de tamanho n.

• É pouco usado, por ter aplicação em poucos casos.

• Ex: O algoritmo de pesquisa sequêncial em um vetor tem complexidade f(n) = Ω(1)

– A análise assume que o número procurado seria o

– primeiro selecionado na lista.

• Abordagem otimista!



• Definido pela letra grega Θ (Theta)

• Deve-se obter a média dos tempos de execução de todas as entradas de tamanho n, ou baseado em probabilidade de

determinada condição ocorrer

Ex.:

• O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = Θ(n/2)

• Em média será necessário visitar n/2 elementos do vetor até

encontrar o elemento procurado

– Melhor aproximação

– Muito difícil de determinar na maioria dos casos

Análise do Caso Médio



• Representado pela letra grega O

• O maiúsculo. Trata-se da letra grega ômicron maiúscula

• Baseia-se no maior tempo de execução sobre todas as entradas de tamanho n

• É o método mais fácil de se obter.

Ex.:

• O algoritmo de pesquisa sequencial em um vetor tem complexidade f(n) = O(n)

• No pior caso será necessário visitar todos os n elementos do

vetor até encontrar o elemento procurado

– Abordagem pessimista!

Análise do Pior Caso



• Tempo (ou espaço) é contabilizado em número de passos do

algoritmo (unidade de armazenamento)

• Análise do algoritmo determina uma função que depende do tamanho da entrada n.

Ex:

• 10n³ + 4n -10

– À medida que n aumenta, o termo cúbico começa a dominar

– A constante do termo cúbico tem relativamente a mesma importância

que a velocidade da CPU

A Notação O



A Notação O

• Desprezar constantes aditivas ou multiplicativas

– Número de passos 3n será aproximado para n

• Interesse assintótico

– Termos de menor grau podem ser desprezados

•n² + n será aproximado para n²

•6n³ + 4n - 9 será aproximado para n³



• Foi visto que, para calcular a complexidade de um algoritmo,

deve-se analisar o pior caso

• A análise deve ser feita de acordo com a tabela a seguir

Cálculo da Complexidade



1 +

1 +

1 +

n * (

n * (

n * (

1 +

1 +

1 +

3

)

)

)

1 +

1 +

1

Cálculo da Complexidade: Algoritmo Iterativo



1 +

1 +

1 +

n * (

n * (

n * (

1 +

1 +

1 +

3

)

)

)

1 +

1 +

1

Cálculo da Complexidade: Algoritmo Iterativo



• A questão se complica um pouco quando se trata de algoritmos

recursivos

• Embora não haja um método único para esta avaliação, a

complexidade de um algoritmo recursivo é definida em função de

componentes como:

– Complexidade da base

– Complexidade do Núcleo

– Profundidade da Recursão

• Número de vezes que o procedimento recursivo é invocado

• Depende do tamanho do problema e da taxa de redução do

tamanho do problema

• É justamente em sua determinação que reside o problema!

Cálculo da Complexidade: Algoritmo Recursivo



Cálculo da Complexidade: Algoritmo Recursivo

• A redução se dá de uma em uma unidade, de n até chegar a

0

– Logo, a profundidade da recursão é n

• Tanto o núcleo quando a base executam apenas uma

operação

– A base é executada uma única vez e o núcleo n - 1 vezes

• Logo, o número de operações executadas é ((n – 1) *1)

+ 1, resultando em uma complexidade O(n)



• Complexidade Constante

• Complexidade Linear

• Complexidade Logarítmica

• Complexidade Log Linear

• Complexidade Quadrática

• Complexidade Cúbica

• Complexidade Exponencial

• Complexidade Fatorial

Ordens de Algoritmos



• São os algoritmos onde a complexidade independe do tamanho n de entradas

• É o único em que as instruções dos algoritmos são

executadas um número fixo de vezes

Complexidade Constante – O(1)



• Uma operação é realizada em cada elemento de entrada,

• Ex.: pesquisa de elementos em uma lista

Complexidade Linear – O(N)



• Ocorre tipicamente em algoritmos que dividem o problema

em problemas menores

Complexidade Logarítmica – O(logn)



• Ocorre tipicamente em algoritmos que dividem o problema

em problemas menores, porém juntando posteriormente a

solução dos problemas menores

Complexidade Log Linear – O(nLOGn)



• Itens são processados aos pares, geralmente com um loop

dentro do outro

Complexidade Quadrática – O(n²)



• Itens são processados três a três, geralmente com um loop

dentro do outros dois

Complexidade Cúbica – O(n³)



• Utilização de “Força Bruta” para encontrar a solução de um

problema.

• A solução geralmente é baseada diretamente no enunciado

do problema e nas definições dos conceitos envolvidos

Ex:

• Utilizando apenas números é possível criar 10n senhas de n

dígitos

• Um algoritmo de força bruta para quebrar uma dessas senhas tem complexidade O(2n)

Complexidade Exponencial – O(2n)



• Também é baseada na utilização de força bruta para encontrar a

solução de um problema

• Consiste em testar todas as possíveis permutações existentes

na solução à procura da solução ótima para o problema

• Ex.: Problema do Caixeiro Viajante

– Encontrar a rota mínima para visitar várias cidades sem repetir

nenhuma

– É um problema base para o projeto de microchips, sequenciamento de

genoma e muitas outras aplicações

– Não possui solução exata eficiente (Problema NP)

– Utilização de heurísticas para aproximar a solução ótima

Complexidade Fatorial – O(n!)



• Imagine um computador que leva 1ms para executar uma

operação.

• A tabela abaixo indica o tempo aproximado de execução de

um algoritmo com diferentes ordens de complexidades para 3

tamanhos de entrada

Ordens de Complexidade



• Todas as ordens de complexidade vistas definem o Limite

Superior (Upper Bound) dos Algoritmos

– Qualquer que seja o tamanho da entrada, o tempo de execução

crescerá com velocidade igual ou inferior a apontada pela análise de

complexidade.

– Algumas otimizações podem ser feitas para melhorar o limite superior;

• Existem, porém, os Limites Inferiores (Lower Bound) para

certos problemas, que são pontos a partir dos quais não é

mais possível otimizar uma solução algorítmica

Limites Superior e Inferior




• Dado um problema de Multiplicação de 2 matrizes N X N.

• A solução trivial tem complexidade O(n³);

– Sabemos assim que a complexidade deste problema não deve superar O(n³), uma vez que existe um algoritmo com está ordem

complexidade que o resolve;

• Este limite superior de um algoritmo pode mudar se alguém

descobrir um algoritmo melhor.




• Strassen resolveu o problema com uma complexidade de O(nlog7)

– Outros pesquisadores melhoraram ainda mais este resultado.

– Atualmente o melhor resultado é o de Coppersmith e Winograd de O(n2.376).

• O limite superior de um algoritmo é parecido com o recorde

mundial de uma modalidade de atletismo.

• Ele é estabelecida pelo melhor atleta (algoritmo) do

momento. Assim como o recorde mundial, o limite superior

pode ser melhorado por um algoritmo (atleta) mais veloz.




• Às vezes é necessário mostrar que, para um dado problema,

qualquer que seja o algoritmo a ser usado, requer um certo

número mínimo de operações: o Limite Inferior

• Para o problema de multiplicação de matrizes de ordem n,

apenas para ler os elementos das duas matrizes de entrada leva O(n²). Assim uma cota inferior trivial é Ω(n²).




• Na analogia anterior, o limite inferior não dependeria mais do

atleta.

– Seria algum tempo mínimo que a modalidade exige, qualquer que seja

o atleta.

– Um limite inferior trivial para os 100 metros seria o tempo que a

velocidade da luz leva para percorrer 100 metros no vácuo.

• Se um algoritmo tem uma complexidade que é igual ao limite

inferior do problema então o algoritmo é ótimo.

• O algoritmo de CopperSmith e Winograd é de O(n2.376) mas

o limite inferior é de Ω(n²).

– Portanto não é ótimo. Este limite superior ainda pode ser melhorado



Exercício

• Efetuar o cálculo de complexidade dos algoritmos

apresentados no início da unidade

Documents

ALGORITMOS AVANÇADOS UNIDADE I Análise de Algoritmo ...luizleao.com/Docencia/FAP/ALGAVANC/ALGORITMO_AVANC_UND_01.pdf · –É um problema base para o projeto de microchips, sequenciamento