Análise de Algoritmos [1] - fenix.tecnico.ulisboa.pt · Algoritmos e Estruturas de Dados - C 1 Algoritmos e Estruturas de Dados MEE – 2014/2015 Análise de Algoritmos e Complexidade

Algoritmos e Estruturas de Dados - C

1

Algoritmos e Estruturas de Dados MEE – 2014/2015

Análise de Algoritmos e Complexidade

Análise de Algoritmos [1]

AED (IST/DEEC) 2

}  Para avaliar e comparar o desempenho de dois algoritmos: }  executamos ambos (muitas vezes) para ver qual é mais rápido }  fornece indicações sobre o desempenho e informação sobre como

efectuar uma análise mais profunda }  Método empírico pode consumir demasiado tempo

}  é necessário uma análise mais detalhada para validar resultados }  Que dados usar?

}  dados reais: verdadeira medida do custo de execução }  dados aleatórios: assegura-nos que as experiências testam o algoritmo

e não apenas os dados específicos }  Caso médio

}  dados perversos: mostram que o algoritmo funciona com qualquer tipo de dados }  Pior caso!

}  dados benéficos: }  Melhor caso


2


AED (IST/DEEC) 3

}  Melhorar algoritmos }  Analisando o seu desempenho }  Fazendo pequenas alterações para produzir um novo algoritmo }  Identificando as abstracções essenciais do problema }  Comparando algoritmos com base no seu uso dessas abstracções

}  Por vezes ignoram-se as características essenciais de desempenho }  Aceita-se um algoritmo mais lento para evitar analisá-lo ou fazer

alterações complicadas }  É no entanto possível obter tremendos aumentos de desempenho

escolhendo/desenvolvendo o algoritmo certo


AED (IST/DEEC) 4

}  Evitar perder demasiado tempo a estudar essas características }  para quê optimizar o desempenho de um algoritmo que

}  já é rápido no contexto da sua utilização }  é utilizado com poucos dados }  ou é pouco utilizado (executado)


3


AED (IST/DEEC) 5

}  É fundamental para percebermos um algoritmo de forma a tomarmos partido dele de forma efectiva/eficiente }  compararmos com outros }  prevermos o desempenho }  escolher correctamente os seus parâmetros

}  Importante saber que há bases científicas irredutíveis para caracterizar, descrever e comparar algoritmos

}  Intenção nesta disciplina é }  ilustrar o processo }  introduzir alguma notação }  introduzir este tipo de análise demonstrando a sua utilidade e

importância


AED (IST/DEEC) 6

}  Análise precisa é uma tarefa complicada: }  algoritmo é implementado numa dada linguagem }  linguagem é compilada e o programa é executado num dado

computador }  difícil prever tempos de execução de cada instruções e antever

optimizações }  muitos algoritmos são "sensíveis" aos dados de entrada }  muitos algoritmos não são bem compreendidos

}  É em geral, no entanto, possível prever aproximadamente o tempo de execução de um programa, }  ou que um algoritmo é melhor que outro em dadas circunstâncias (bem

definidas) }  apenas é necessário um pequeno conjunto de ferramentas matemáticas


4


AED (IST/DEEC) 7

}  Fundamental é separar a análise da implementação, i.e. identificar as operações de forma abstracta }  é relevante saber quantas vezes id[p] é acedido

}  Uma propriedade (imutável) do algoritmo

}  não é tão importante saber quantos nanosegundos essa instrução demora no meu computador! }  Uma propriedade do computador e não do algoritmo

}  O número de operações abstractas pode ser grande, mas }  o desempenho tipicamente depende apenas de um pequeno número de

parâmetros }  procurar determinar a frequência de execução de cada um desses

operadores }  estabelecer estimativas


AED (IST/DEEC) 8

}  Dependência nos dados de entrada }  dados reais geralmente não disponíveis: }  assumir que são aleatórios: caso médio

}  por vezes a análise é complicada }  Pode ser uma ficção matemática não representativa da vida real

}  perversos: pior caso }  por vezes difícil de determinar }  podem nunca acontecer na vida real

}  benéficos: melhor caso

}  Em geral são boas indicações quanto ao desempenho de um algoritmo


5

Análise: Crescimento de Funções [1]

AED (IST/DEEC) 9

}  O tempo de execução geralmente dependente de um único parâmetro N }  ordem de um polinómio }  tamanho de um ficheiro a ser processado, ordenado, etc. }  ou medida abstracta do tamanho do problema a considerar

}  usualmente relacionado com o número de dados a processar

}  Quando há mais de um parâmetro }  procura-se exprimir todos os parâmetros em função de um só }  faz-se uma análise em separado para cada parâmetro


AED (IST/DEEC) 10

}  Os Algoritmos têm tempo de execução proporcional a: }  1

}  muitas instruções são executadas uma só vez ou poucas vezes }  se isto for verdade para todo o programa diz-se que o seu tempo de

execução é constante }  log N

}  tempo de execução é logarítmico }  cresce ligeiramente à medida que N cresce }  usual em algoritmos que resolvem um grande problema reduzindo-o a

problemas menores e resolvendo estes }  quando N duplica log N aumenta mas muito pouco; apenas duplica quando N

aumenta para N2 }  N

}  tempo de execução é linear }  típico quando algum processamento é feito para cada dado de entrada }  situação óptima quando é necessário processar N dados de entrada (ou

produzir N dados na saída)


6


AED (IST/DEEC) 11

}  N log N }  típico quando se reduz um problema em sub-problemas, se resolve estes

separadamente e se combinam as soluções }  se N é 1 milhão N log N é perto de 20 milhões

}  N2

}  tempo de execução quadrático }  típico quando é preciso processar todos os pares de dados de entrada }  prático apenas em pequenos problemas (ex: produto matriz - vector)

}  N3

}  tempo de execução cúbico }  para N = 100, N3 = 1 milhão (ex: produto de matrizes)

}  2N

}  tempo de execução exponencial }  provavelmente de pouca aplicação prática }  típico em soluções de força bruta }  para N = 20, 2N = 1 milhão; N duplica, tempo passa a ser o quadrado (ex:

cálculo da saída de um circuito lógico de N entradas )


AED (IST/DEEC) 12

}  Outros exemplos são }  log log N }  log* N (número de logs até 1)

}  Usualmente muito mais pequenas (quase constantes)

}  Valores típicos de várias funções

3 3 10 33 110 32 100

7 10 100 664 4414 1000 10000

10 32 1000 9966 99317 31623 1000000

13 100 10000 132877 1765633 1000000 100000000

17 316 100000 1660964 27588016 31622777 10000000000

20 1000 1000000 19931569 397267426 1000000000 1000000000000


7

Análise: Resolução de grandes problemas [1]

AED (IST/DEEC) 13

}  Relação do tempo de execução }  conversão para unidades de tempo mais familiares

Segundos

102 1.7 minutos

104 2.8 horas

105 1.1 dias

106 1.6 semanas

107 3.8 meses

108 3.1 anos

109 3.1 décadas

1010 3.1 séculos

1011 nunca

Análise: Resolução de grandes problemas [2]

AED (IST/DEEC) 14

Operações por

segundo

Tamanho do problema 1 milhão

Tamanho do problema 1 bilião

N NlgN N2 N NlgN N2

106 segundos segundos semanas horas horas nunca

109 instantâneo instantâneo horas segundos segundos décadas

1012 instantâneo instantâneo segundos instantâneo instantâneo semanas


8

Análise: Complexidade

AED (IST/DEEC) 15

}  Complexidade refere-se ao tempo de execução }  usualmente o termo de maior ordem domina (para N elevado) }  comum todos os termos serem multiplicados por uma constante }  para N pequeno vários termos podem ser igualmente relevantes

}  ex: 0.1 N3 + 100 * N2 para 1 ≤ N ≤ 1000

}  base do logaritmo não é muito relevante }  Mudar de base é um factor constante: ln x = ln b * logb x

}  Bases mais comuns são 2 (lg N), 10 (log N) e e (ln N)

¨  [e = número de Neper]

}  Análise de complexidade é muito importante quando N aumenta

Análise: Funções Relevantes

AED (IST/DEEC) 16

função nome valores típicos aproximação

floor (chão)

ceiling (tecto)

logaritmo binário

números de Fibonacci

números harmónicos

função factorial

= 2.71828...

= 0.57721...

=

= 0.693147...

=


9

Análise: Sucessões

AED (IST/DEEC) 17

}  Números Harmónicos – área debaixo da curva de 1/x entre 1 e N (integração)

γ = 0.57721... (constante de Euler) }  é uma boa aproximação (reflecte diferença entre HN e o integral)

}  Números de Fibonacci para N ≥ 2 com F0 = 0 e F1 = 1

}  Fórmula de Stirling

}  e muitas outras: }  distribuição binomial }  aproximação de Poisson

}  etc.

Análise: Notação “O”, “Ω” e “Θ”

AED (IST/DEEC) 18

}  Definição 1 – Uma função g(N) diz-se ser O(f(N)), escrevendo-se

se existem constantes c0 e N0 tais que 0 ≤ g(N) ≤ c0f(N) para qualquer N ≥ N0.

}  Definição 2 – Uma função g(N) diz-se ser Ω(f(N)), escrevendo-se

se existirem constantes c0 e N0 tais que g(N) ≥ c0f(N) ≥ 0 para qualquer N ≥ N0.

}  Definição 3 – Uma função g(N) diz-se ser Θ(f(N)), escrevendo-se

se g(N) ∈ O(f(N)) e g(N) ∈ Ω(f(N)) .


10

Notação “O” - Representação Gráfica

AED (IST/DEEC) 19

g(N)

f(N) c0f(N)

N0

}  Limitar uma função com uma aproximação O }  g(N) ∈ O(f(N)) }  g(N) debaixo de uma curva com

o andamento de f(N) a par7r de um dado N

}  g(N) proporcional a f(N) }  g() eventualmente cresce

como f(), a menos de uma constante

Análise: Aproximação funcional

AED (IST/DEEC) 20

}  g(N) é como f(N) }  Permite usar f() para es7mar

<<g()


11

Análise: Para que serve a notação?

AED (IST/DEEC) 21

}  Esta notação matemática permite suprimir detalhes na análise de algoritmos

}  A notação é usada com três objectivos: }  limitar o erro que é feito ao ignorar os termos menores nas fórmulas

matemáticas; }  limitar o erro que é feito na análise ao desprezar parte de um programa

que contribui de forma mínima para o custo/complexidade total; }  permitir-nos classificar algoritmos de acordo com limites superiores e

inferiores no seu tempo de execução.

}  Notar que O(f(N)), Ω(f(N)) e Θ(f(N)) representam conjuntos de funções

}  Existem pares de funções para as quais não é possível determinar a existência de nenhuma daquelas relações

Análise: Notação “O” [1]

AED (IST/DEEC) 22

}  Os Resultados da análise não são exactos }  são aproximações tecnicamente bem caracterizadas

}  Manipulações com a notação “O” }  permitem-nos ignorar termos de menor importância de forma precisa }  podem ser feitas como se o “O” não estivesse lá

}  Ex: usando distributividade e o facto de que

se f(N) não for constante fica

e como


12

Análise: Notação “O” [2]

AED (IST/DEEC) 23

}  Manipulações com a notação “O” – alguns exemplos

}  Fórmula com termo contendo O(...) diz-se expressão assimptótica }  Porque se refere ao comportamento da função quando N cresce

para infinito

Exemplo: vantagens da notação [1]

AED (IST/DEEC) 24

}  Dado um problema para análise }  verifica-se ter um loop interno iterado 2NHN vezes em média

}  cada iteração requer execução de a0 instruções (ou demora a0 ns)

}  secção interna iterada N vezes }  requer execução de a1 instruções (ou demora a1 ns)

}  inicialização feita uma vez }  requer execução de a2 instruções (ou demora a2 ns)

}  Complexidade (tempo médio de execução) é

}  Para N grande não é preciso calcular a1 ou a2


13

Exemplo: vantagens da notação [2]

AED (IST/DEEC) 25

}  Usando a notação 𝒪() temos }  Logo

}  O que acontece quando N duplica?

}  Também não é preciso conhecer o valor de a0!

Operações sobre dados - Complexidade

AED (IST/DEEC) 26

}  As operações sobre dados mais usadas são quatro:

1.  Acesso }  Ver se existe, e recolher, o valor do conteúdo de um elemento

2.  Modificação }  Alterar o valor do conteúdo de um elemento

3.  Inserção }  Acrescentar um novo elemento e/ou componente a uma estrutura já

existente

4.  Remoção }  Apagar um elemento e/ou componente de uma estrutura já existente


14

Acesso e modificação de variáveis

AED (IST/DEEC) 27

}  Na operação de acesso a dados organizados em tabela ou lista pode-se querer }  Aceder ao primeiro elemento }  Aceder ao último elemento }  Aceder a um elemento específico }  Aceder ao próximo (pressupõe a existência de um cursor)

}  Em operações de modificação pode-se também querer }  Modificar o conteúdo do primeiro elemento }  Modificar o conteúdo do último elemento }  Modificar o conteúdo de um elemento específico }  Modificar o próximo (pressupõe a existência de um cursor)

Eficiência no acesso e modificação

AED (IST/DEEC) 28

}  A eficiência nas operações de acesso e modificação é condicionada pela estrutura escolhida para armazenar os dados

}  Assim Acesso/

Modificação Tabela Lista

Primeiro 𝒪(1) 𝒪(1) Último 𝒪(1) 𝒪(N)

Próximo 𝒪(1) 𝒪(1) Específico 𝒪(1) 𝒪(k)

Assume-se

que apenas

existe um

ponteiro para

o início da

lista.

N é o número de elementos existentes k é a posição do elemento a aceder ou modificar (N ≥ k)


15

Inserção de componentes

AED (IST/DEEC) 29

}  Na operação de inserção de novos elementos em tabelas, ou em listas, pode pretender-se }  Inserir um novo elemento na primeira posição, deslocando todos os

outros para a frente.

}  Inserir um novo elemento na última posição sem afectar os já existentes.

}  Inserir um novo elemento numa posição intermédia pré-especificada, sem afectar os anteriores e deslocando os posteriores para a frente.

}  Inserir um novo elemento de acordo com o seu valor ou em função do valor de algum qualificador associado com esse elemento.

Eficiência na inserção

AED (IST/DEEC) 30

}  A eficiência da operações de inserção é condicionada pela estrutura escolhida para armazenar os dados

}  Assim

Inserção Tabela Lista Primeiro 𝒪(N) 𝒪(1) Último 𝒪(1) 𝒪(N) Pré-

especificado 𝒪(N-k) 𝒪(k)

Condicional 𝒪(N) 𝒪(k)

N é o número de elementos existentes antes da inserção k é a posição onde ficará o elemento a inserir (N ≥ k)

Assume-se

que apenas

existe um

ponteiro para

o início da

lista.


16

Remoção de componentes

AED (IST/DEEC) 31

}  Na operação de remoção de elementos de tabelas ou de listas pode pretender-se }  Apagar o primeiro elemento da primeira posição, deslocando todos os

outros para trás.

}  Apagar o último elemento sem afectar os já existentes. }  Apagar o elemento situado numa posição intermédia pré-especificada,

sem afectar os anteriores e deslocando os posteriores para trás.

}  Apagar o elemento que possuir determinado valor, propriedade, etc.

Eficiência na remoção

AED (IST/DEEC) 32

}  A eficiência da operações de remoção é condicionada pela estrutura escolhida para armazenar os dados

}  Assim

Remoção Tabela Lista Primeiro 𝒪(N) 𝒪(1) Último 𝒪(1) 𝒪(N) Pré-

especificado 𝒪(N-k) 𝒪(k)

Condicional 𝒪(N) 𝒪(k)

N é o número de elementos existentes antes da remoção k é a posição onde está o elemento a remover (N ≥ k)

Assume-se

que apenas

existe um

ponteiro para

o início da

lista.


17

Análise – Síntese da Aula 1

AED (IST/DEEC) 33

}  Análise de Algoritmos }  Aspectos essenciais da análise

}  empírica, teórica; estratégias de melhoria de algoritmos; comparação de algoritmos

}  Crescimento de funções }  Resolução de grandes problemas }  Complexidade, funções relevantes e sucessões }  Notação Assimptótica

}  Conceito }  Definições }  Propriedades

}  Operações sobre dados }  determinação da complexidade

Instruções básicas [1]

AED (IST/DEEC) 34

}  Para fazer a análise do tempo de execução de um dado algoritmo ou troço de código, introduz-se o conceito de instrução básica ou elementar;

}  Definição: Instrução básica }  É uma instrução cujo tempo de execução pode ser limitado

superiormente por uma constante. Essa constante pode variar de máquina para máquina e, numa mesma máquina, pode ser diferente para diferentes tipos de instruções básicas.

}  Exemplos:

id[p] = j; a = 3*b[i]; x = sqrt(c[j]); i++; if (i < N)... /* etc. */


18


AED (IST/DEEC) 35

}  Em geral todas as operações aritméticas elementares, como somas, subtrações, multiplicações e divisões, são operações básicas; }  Exceptuam-se os casos de multiplicações de inteiros muito grandes, por

exemplo.

}  A maioria das chamadas a funções das bibliotecas são operações básicas; }  Por exemplo, as chamadas às funções matemáticas sqrt(), cos(),

etc., são básicas.

}  As instruções de atribuição e de teste/comparação são também operações básicas;

}  A instrução abaixo não é básica em geral, se N for a variável que condiciona o tamanho do problema que se está a tratar. a[i] = minha_funcao(N);


AED (IST/DEEC) 36

}  Para analisar um troço de código é necessário identificar quais as instruções básicas e quais as que o não são.

}  As instruções que não são básicas são, em geral, descritas por uma sequência de instruções básicas; }  Analisam-se estas individualmente.

}  Assim, depois de identificar quais os elementos básicos, os não básicos e analisar estes últimos, é possível expressar quantas instruções básicas são executadas no total, como função do tamanho do problema;

}  A análise de complexidade de um algoritmo consiste na determinação da função que relaciona a dimensão do problema com o número de instruções básicas executadas. }  Que é o mesmo que dizer com o tempo de execução.


19

Metodologia para determinação de complexidade [1]

AED (IST/DEEC) 37

}  Suponha o seguinte código

}  A contabilização do número de instruções é simples }  N iterações e em cada uma é executado um número constante de

instruções básicas – 𝒪(N) }  Suponha o código seguinte

}  A contabilização do número de instruções é ainda simples }  O ciclo interno é 𝒪(N) e é executado N vezes – 𝒪(N2)

for (i = 0; i < N; i++) { instruções básicas; }

for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { instruções básicas; } }


AED (IST/DEEC) 38

}  Suponha o código seguinte

}  A contabilização do número de instruções é ainda simples }  O ciclo interno é executado N + (N-1) + (N-2) + … + 3 + 2 + 1 = N(N+1)/2 ∈ 𝒪(N2)

}  Infelizmente, nem sempre a contabilização é assim tão simples...

for (i = 0; i < N; i++) { for (j = i; j < N; j++) { instruções básicas; } }


20


AED (IST/DEEC) 39

}  Suponha o seguinte código

}  A contabilização do número de instruções não parece ser simples }  Numa chamada à função executamos

}  algumas instruções sobre N objectos (digamos f(N); pode ser constante, N, etc.)

}  depois voltamos a chamar a mesma função agora apenas com N-1 objectos.

}  O número total de instruções básicas executadas é descrito por uma recorrência!

void func(int a[], int N) { várias instruções básicas; func(a, N-1); return; }


AED (IST/DEEC) 40

}  Para além da análise do tempo de execução, poderemos necessitar de fazer a análise da memória utilizada por um dado algoritmo

}  Nestas circunstâncias, as instruções de interesse dizem respeito à definição de variáveis, seja em tempo de compilação ou de execução.

}  Exemplos:

void exemplo1(int N, ...) { int i; ... }

void exemplo2(int N, ...) { int *vector; vector = (int *) malloc(N*sizeof(int)); ... }


21


AED (IST/DEEC) 41

}  Para além da análise do tempo de execução, poderemos necessitar de fazer a análise da memória utilizada por um dado algoritmo

}  Nestas circunstâncias, as instruções de interesse dizem respeito à definição de variáveis, seja em tempo de compilação ou de execução.

}  Exemplos:

void exemplo1(int N, ...) { int i; ... }

void exemplo2(int N, ...) { int vector[N]; ... }


AED (IST/DEEC) 42

}  Para cada função há que contabilizar as variáveis usadas

}  Neste caso temos que incluir também a memória usada pela

função exemplo4

void exemplo3(int N, ...) { int i, *vector; vector = (int *) malloc(N*sizeof(int)); ... for (i=0; i<N; i++){ vector[i] = exemplo4(i); } ... }


22


AED (IST/DEEC) 43

}  Para cada função há que contabilizar as variáveis usadas

}  Neste caso temos que incluir também a memória usada pela

função exemplo4

void exemplo3(int N, ...) { int i; int vector[N]; ... for (i=0; i<N; i++){ vector[i] = exemplo4(i); } ... }


AED (IST/DEEC) 44

}  Notar que, apesar de existirem duas chamadas recursivas à função, elas não coexistem ao mesmo tempo.

}  Assim, apenas se contabiliza uma das chamadas

void exemplo5(int N, ...) { algumas alocações; /* f(N) */ ... algumas instruções; ... exemplo5(N/2, ...); ... mais instruções; ... exemplo5(N/2, ...); ... }

}  Tal como acontece para a determinação da complexidade temporal, a determinação da complexidade de memória para funções recursivas requer tratamento especial


23

Análise: Recorrências básicas [1]

AED (IST/DEEC) 45

}  Muitos algoritmos são baseados na ideia de “dividir para conquistar” }  dividir recursivamente um problema grande em vários problemas

menores }  recursividade é uma técnica muito efectiva (estudaremos

posteriormente) }  É importante perceber como analizar algumas fórmulas

standard }  intervêm muitas vezes na análise de muitos algoritmos }  permite compreender os métodos básicos de análise


AED (IST/DEEC) 46

}  Seja um programa recursivo que, em cada passo, analisa todos os dados de entrada para eliminar um item }  Para um problema de tamanho N executa 𝒪(N) instruções básicas }  Depois tem que resolver um problema de tamanho N-1

para N ≥ 2 e C1 = 1

}  Solução }  CN é aproximadamente igual

a N2/2 }  Demonstração

}  usar a propriedade telescópica e aplicar a fórmula a si própria

}  Importante }  O carácter recursivo de um

algoritmo reflecte-se directamente na sua análise


24


AED (IST/DEEC) 47

}  Seja um programa recursivo que, em cada passo, após a execução de um número fixo de instruções básicas reduz o problema a metade }  Para um problema de tamanho N executa 𝒪(1) instruções básicas }  Depois tem que resolver um problema de tamanho N/2

para N ≥ 2 e C1 = 1

}  Solução }  CN é aproximadamente igual a log N

}  Demonstração }  Fazer N =2k, usar a propriedade telescópica que

dá CN = 𝒪(k). Como k = log N, CN = 𝒪(log N) }  Importante

}  se N/2 for ⎣N/2⎦, então CN é o número de bits na representação binária de N, logo é ⎣lg N⎦ +1


AED (IST/DEEC) 48

}  Seja um programa recursivo que, em cada passo, examina todos os items para resolver depois metade do problema original }  Para um problema de tamanho N executa 𝒪(N) instruções básicas }  Depois tem que resolver um problema de tamanho N/2

para N ≥ 2 e C1 = 1

}  Solução }  CN é aproximadamente igual a 2N

}  Demonstração }  usar a propriedade telescópica e aplicar a fórmula a si

própria }  A recorrência leva à soma N + N/2 + N/4 + N/8 + . . . }  Se a sequência for infinita, a soma da série geométrica é 2N


25


AED (IST/DEEC) 49

}  Seja um programa recursivo que, em cada passo, tem de examinar todos os dados de entrada antes, durante ou depois de os dividir em duas metades para processamento }  Para um problema de tamanho N executa 𝒪(N) instruções básicas }  Depois tem que resolver dois problemas de tamanho N/2

para N ≥ 2 e C1 = 1

}  Solução }  CN é aproximadamente N lg N

}  Demonstração }  Fazer N = 2k , aplicar o método

telescópico que produz CN = C2k = k2k. }  Sendo k = log N, CN = 𝒪(N lg N)


AED (IST/DEEC) 50

}  Seja um programa recursivo que, em cada passo, divide os dados de entrada em dois e depois realiza um número constante de outras operações }  Para um problema de tamanho N executa 𝒪(1) instruções básicas }  Depois tem que resolver dois problemas de tamanho N/2

para N ≥ 2 e C1 = 1

}  Solução }  CN é aproximadamente 2N

}  Demonstração }  Como a anterior


26

O “Master Theorem”

AED (IST/DEEC) 51

}  Teorema: Sejam a ≥ 1 e b > 1 constantes, seja f(n) uma função e seja T(n) definida para todos os inteiros não negativos pela recorrência T(n) = a T(n/b) + f(n), em que se interpreta n/b como podendo significar ⎣n/b⎦ ou ⎡n/b⎤. Então T(n) pode ser limitada assimptoticamente da seguinte forma:

1.  Se f(n) = 𝒪(nlogba – ε) para alguma constante ε > 0, então T(n) =Θ(nlogba). (nlogba – ε) para alguma constante ε > 0, então T(n) =Θ(nlogba). 2.  Se f(n) = Θ(nlogba lgk n), então T(n) = Θ(nlogba lgk+1 n). 3.  Se f(n) = Ω(nlogba + ε) para alguma constante ε > 0, e se af(n/b) ≤ cf(n)

para alguma constante c < 1 e todo o n suficientemente grande, então T(n) = Θ(f(n)).

Exemplo de aplicação do teorema

AED (IST/DEEC) 52

}  Apliquemos o teorema à recorrência CN = 2CN/2 + N }  a = 2 e b = 2, logo

Nlogba = N }  f(N) = N, ou seja, f(N) ∈ Θ(Nlogba), para ε = 0 e k = 0. }  Então, pela aplicação do teorema se conclui que

CN ∈ Θ(NlogbalgN) = Θ(N lgN) como se viu no acetato 47.


27

Exemplos adicionais

AED (IST/DEEC) 53

}  Exemplo 2: T(n) = 9 T(n/3) + n }  a = 9, b = 3, f(n) = n }  nlogba = nlog39 = Θ(n2) }  f(n) = O(nlog39 – ε), com ε = 1, }  caso 1 → T(n)= Θ(n2)

}  Exemplo 3: T(n) = T(2n/3) + 1 }  a = 1, b = 3/2, f(n) = 1 }  nlogba = nlog3/21 = Θ(n0)=1 }  f(n) = O(nlog39 – ε)= Θ(1), }  caso 2 → T(n)= Θ(lg n)

Análise: Procura sequencial e procura binária

AED (IST/DEEC) 54

}  Dois algoritmos básicos que nos permitem ver se um elemento de uma sequência de objectos aparece num conjunto de objectos previamente guardados }  permite ilustrar o processo de análise e comparação de algoritmos

}  Exemplo de aplicação }  companhia de cartões de crédito quer saber se as últimas M transacções

envolveram algum dos N cartões dados como desaparecidos ou de maus pagadores

}  Pretende-se estimar o tempo de execução dos algoritmos }  N é muito grande (ex: 104 a 106) e M enormíssimo (106 a 109)


28

Procura Sequencial - Solução trivial

AED (IST/DEEC) 55

}  Assumir que }  os objectos são representados por números inteiros }  dados armazenados numa tabela }  procura é sequencial na tabela

int search (int a[], int v, int l, int r) { int i; for (i = l; i <= r; i++) if (v == a[i]) return i ; return –1; }

Procura Sequencial - Solução trivial Análise [1]

AED (IST/DEEC) 56

}  O tempo de execução depende se o objecto está ou não na tabela }  se não estiver percorremos a tabela toda (N elementos) }  se estiver podemos descobrir logo no início (ou no fim) }  tempo depende dos dados!

}  Assumir algo sobre os dados }  números são aleatórios (não relacionados entre si) ?? }  esta propriedade é critica!

}  Assumir algo sobre a procura }  estudar o caso de sucesso e o de insucesso separadamente }  tempo de comparação assumido constante


29

Procura Sequencial - Solução trivial Análise [2]

AED (IST/DEEC) 57

}  Propriedade: na procura sequencial o número de elementos da tabela que são examinados é: }  N em caso de insucesso }  em média aproximadamente N/2 em caso de sucesso }  Tempo de execução é portanto proporcional a N (linear)! }  Isto para cada elemento de entrada

}  Custo total é 𝒪(MN) que é enorme (MN) que é enorme

}  Como melhorar o algoritmo? }  manter os números ordenados na tabela (estudaremos algoritmos de

ordenação nos capítulos seguintes) }  na procura sequencial numa tabela ordenada o custo é N no pior caso e

N/2 em média (quer haja sucesso ou não)

Procura Binária [1]

AED (IST/DEEC) 58

}  Se demorar c microsegundos a examinar um número e M=109, N=106

}  tempo total de verificação são 16 c anos !!

}  Ideia: se os números na tabela estão ordenados podemos eliminar metade deles comparando o que procuramos com o que está na posição do meio }  se for igual temos sucesso (sorte!) }  se for menor aplicamos o mesmo método à primeira metade da tabela }  se for maior aplicamos o mesmo método à segunda metade da tabela


30

Procura Binária [2]

AED (IST/DEEC) 59

int search (int a[], int v, int l, int r) { while (r >= l) { int m = (l+r)/2; if (v == a[m]) return m; if (v < a[m]) r = m-1; else l = m+1; } return –1; }

Procura Binária - Análise

AED (IST/DEEC) 60

}  Propriedade: A procura binária nunca examina mais do que ⎣lg N⎦ + 1 números

}  Demonstração: (ilustra uso de recorrências) }  Seja TN o número de comparações no pior caso; redução em 2 implica

TN ≤ T ⎣N/2⎦ + 1 para N ≥ 2 com T1 = 1, i.e., após uma comparação ou temos sucesso ou continuamos a procurar numa tabela com ⎣N/2⎦ elementos

}  Sabemos de imediato que TN ≤ n+1 (em que N = 2n) e o resto segue por indução matemática)

}  Mostra que este tipo de pesquisa permite resolver problemas até um milhão de dados com cerca de 20 comparações por procura }  possivelmente menos do que o tempo que demora a ler ou escrever os

números num computador real


31

Estudo empírico de algoritmos de procura

AED (IST/DEEC) 61

M = 1000 M = 10000 M = 100000

N S B S B S B

125 1 1 13 2 130 20

250 3 0 25 2 251 22

500 5 0 49 3 492 23

1250 13 0 128 3 1276 25

2500 26 1 267 3 28

5000 53 0 533 3 30

12500 134 1 1337 3 33

25000 268 1 3 35

50000 537 0 4 39

100000 1269 1 5 47

Conclusões da análise do exemplo

AED (IST/DEEC) 62

}  Identificação de operações básicas de forma abstracta }  Utilização de análise matemática para estudar a frequência

com que um algoritmo executa essas operações }  Utilizar resultados para deduzir uma estimativa funcional do

tempo de execução }  Verificar e estender estudos empíricos }  Identificar e eventualmente optimizar as características mais

relevantes de um dado algoritmo


32

Garantias, Previsões e Limitações [1]

AED (IST/DEEC) 63

}  O tempo de execução dos algoritmos depende criticamente dos dados.

}  Objectivo da análise é }  eliminar essa dependência }  inferir o máximo de informação assumindo o mínimo possível

}  O estudo do pior caso é importante: }  permite obter garantias máximas

}  se o resultado no pior caso é aceitável, então a situação é favorável }  é desejável utilizar algoritmos com bom desempenho no pior caso

}  se o resultado no pior caso for mau, pode ser problemático }  não sabemos quão provável será aparecerem dados que levem a esse

desempenho }  importante não sobrevalorizar obtenção de valores baixos para o pior

caso }  não é relevante ter um bom algoritmo para o pior caso que é mau para dados

típicos

Garantias, Previsões e Limitações [2]

AED (IST/DEEC) 64

}  O estudo do desempenho no caso médio é atractivo: }  Permite fazer previsões

}  bom quando é possível caracterizar muito bem os dados de entrada (tipo, frequência, etc)

}  mau quando tal não é possível/fácil }  ex: processar texto aleatório num ficheiro versus processar o texto de um

livro de Eça de Queiróz! }  análise pode ser não trivial em termos matemáticos

}  ex: no algoritmo de união rápida

}  saber o valor médio pode não ser suficiente }  podemos ter de saber o desvio padrão ou outras características

}  não permite dizer nada sobre a possibilidade de um algoritmo ser dramaticamente mais lento que o caso médio

}  por vezes aleatoriedade pode ser imposta


33

Análise – Síntese da Aula 2

AED (IST/DEEC) 65

}  Metodologia para determinação de complexidade }  Recorrências básicas }  Exemplo: Procura

}  Procura sequencial }  Procura binária }  Estudo empírico de métodos de procura }  Conclusões do exemplo

}  Listagem da eficiência de operações sobre dados }  para as tabelas e listas

}  Garantias, previsões e limitações

Documents

Análise de Algoritmos [1] - fenix.tecnico.ulisboa.pt · Algoritmos e Estruturas de Dados - C 1 Algoritmos e Estruturas de Dados MEE – 2014/2015 Análise de Algoritmos e Complexidade