AED_2020_2021_01_complexidade

Prévia do material em texto

Algoritmos e Estruturas de Dados
Complexidade
Universidade Autónoma de Lisboa
UAL © 2021 AED: Complexidade 1 / 29
Complexidade
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 2 / 29
Complexidade
UAL © 2021 AED: Complexidade 3 / 29
Complexidade
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 4 / 29
Complexidade
Definição
Existem várias algoritmos possíveis para resolver um problema de programação. Para optar entre
eles, é necessário uma medida objetiva de eficiência.
Essa medida chama-se complexidade, e traduz o custo esperado do algoritmo.
O custo pode referir-se a tempo ou espaço. Um algoritmo pode ser muito rápido, mas exigir
demasiada memória, ou sofrer uma penalização no tempo, se a otimização da utilização de
espaço for importante.
Vamos concentrar-nos principalmente na complexidade temporal dos algoritmos, i.e., o custo
temporal. O custo espacial continua a ser importante, e também vai ser alvo de estudo.
Os custos variam com a quantidade de dados do problema. Com poucos dados, é indiferente
qual a solução a utilizar. Com muitos dados, algoritmos diferentes podem diferir entre segundos
e horas (ou entre KB e GB de RAM) na resolução do mesmo problema.
UAL © 2021 AED: Complexidade 5 / 29
Complexidade
Contagem de operações primitivas
A complexidade temporal de um algoritmo é medida pelo número de operações primitivas
necessárias até terminar a execução.
Uma operação primitiva é, entre outras:
• Afetação de valor a variável
• Acesso à memória relativa de uma referência
• Operação aritmética
• Operação binária
• Acesso a elementos de vetores (ou listas, em Python)
• Chamada de função
• Retorno de função
A operação primitiva tem um custo unitário, e pretendemos contar/estimar a quantidade de
operações envolvidas na execução de um algoritmo.
UAL © 2021 AED: Complexidade 6 / 29
Complexidade
Cenários de complexidade
O tempo que um algoritmo demora a concluir depende não só dos dados disponíveis, mas
também da questão que está a ser colocada. Parâmetros diferentes resultam em tempos
diferentes. Alguns casos são resolvidos rapidamente, com poucas iterações, outros esgotam o
universo de dados.
Nesse sentido é relevante identificar um conjunto de cenários de execução.
Melhor caso: número de operações primitivas no cenário com menos passos possíveis.
Pior caso: número de operações primitivas no cenário com maior número de passos possível.
Caso esperado: número de operações primitivas esperadas para a média de todos os cenários
possíveis.
UAL © 2021 AED: Complexidade 7 / 29
Exemplo
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 8 / 29
Exemplo
Pesquisa em lista ordenada
Pesquisa sequencial
Elemento Células visitadas
5 2
30 6
42 6
100 10
Pior caso: n
Melhor caso: 2
Caso esperado: n/2
Pesquisa dicotómica
Elemento Células visitadas
5 3 (4,1,0)
30 3 (4,7,5)
42 3 (4,7,5)
100 4 (4,7,8,9)
Pior caso: log2n
Melhor caso: 3
Caso esperado: ?
UAL © 2021 AED: Complexidade 9 / 29
Análise assimptótica
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 10 / 29
Análise assimptótica
Análise assimptótica
Os algoritmos envolvem várias operações mas, na sua análise, interessa caraterizar o
comportamento assimptótico da sua complexidade, i.e., quando o número de dados é grande, a
função que melhor aproxima o comportamento do algoritmo.
Exemplo:
def media(l):
num_elementos = len(l)
sum_elementos = 0
for e in l:
sum_elementos += e
return sum_elementos/num_elementos
← 1 operação
← 1 operação
← n iterações
← 1 operação
← 1 operação
A complexidade pode ser descrita pela expressão:
f (n) = 1 + 1 + (n × 1) + 1 = 3 + n
O comportamento assimptótico de f (n) é n.
UAL © 2021 AED: Complexidade 11 / 29
Notação O
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 12 / 29
Notação O
Notação O
É conveniente descrever o comportamento de algoritmos com a sua convergência assimptótica.
Convenciona-se utilizar a notação O.
Considerando duas funções de inteiros para reais, f (n) : Z→ R, e f ∗(n) : Z→ R,
∃c ∈ R,∃n0 ∈ Z+ : c > 0, n0 > 0,∀n ≥ n0, f (n) ≤ cf ∗(n)↔ f (n) = O(f ∗(n))
Na análise da complexidade, podemos utilizar a aproximação f ∗(n) da função f (n), se estas
tiverem o mesmo comportamento assimptótico.
As pequenas diferenças entre as funções são negligenciáveis em grandes volumes de dados, e
indiferentes em pequenos.
A convergência assimptótica tem também o nome de função custo, ou custo do algoritmo.
UAL © 2021 AED: Complexidade 13 / 29
Notação O
Propriedades
Se f (n) = O(f ∗(n)), e g(n) = O(g∗(n)), então,
• f (n) = O(f (n))
• c × f (n) = O(f ∗(n)), ∀c constante
• f (n)× g(n) = O(f ∗(n)× g∗(n))
• f (n) + g(n) = O(max(f ∗(n), g∗(n)))
∃c1>0 , c2>0 ∈ R : f (n) + g(n) ≤ c1f ∗(n) + c2g∗(n)
≤ max(c1, c2)(f ∗(n) + g∗(n))
≤ 2×max(c1, c2)(max(f ∗(n), g∗(n)))
UAL © 2021 AED: Complexidade 14 / 29
Notação O
Complexidade temporal de construções simples
Algumas estruturas de código têm um custo diretamente determinável:
if q(n) then f(n) else g(n)
while q(n) do f(n) : executado m vezes
for x in [0, ..., m] do f(n)
O(max(q∗(n), f ∗(n), g∗(n))
O(max(m, q∗(n), f ∗(n))
O(m × f ∗(n))
UAL © 2021 AED: Complexidade 15 / 29
Funções de referência
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 16 / 29
Funções de referência
Funções de referência
Existem funções que surgem frequentemente na análise do comportamento assimptótico de
algoritmos.
Polinomial
• f (n) = 1
• f (n) = log(n)
• f (n) = n
• f (n) = n × log(n)
• f (n) = n2
• f (n) = n3
Exponencial
• f (n) = an
• f (n) = n!
UAL © 2021 AED: Complexidade 17 / 29
Comparação entre funções
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 18 / 29
Comparação entre funções
1 GFLOP
A tabela mostra a quantidade de operações realizadas por algoritmos com complexidade f (n),
em cada intervalo de tempo, numa máquina com 1GFLOPS (109 floating point operations per
second).
f (n) 1 minuto 1 hora 1 ano
n 6× 1010 3.6× 1012 3.16× 1016
n2 244 949 1 897 367 177 826 882
n3 3 915 15 326 316 227
2n 36 42 55
n! 13 15 18
UAL © 2021 AED: Complexidade 19 / 29
Comparação entre funções
5 GFLOPS
5GFLOPS VS 1GFLOPS representa 20 anos de inovação no mercado de computadores pessoais.
f (n) 1 minuto 1 hora 1 ano
n 3× 1011 1.8× 1013 1.5× 1017
n2 547 723 4 242 641 397 632 997
n3 6 694 26 207 540 740
2n 38 44 57
n! 14 15 19
UAL © 2021 AED: Complexidade 20 / 29
Comparação entre funções
200 PFLOPS
200 PFLOPS representa um dos maiores poderes computacionais do planeta: Summit, US
Department of Energy, Oak Ridge National Laboratory.
f (n) 1 minuto 1 hora 1 ano
n 1.2× 1019 7.1× 1020 6.32× 1024
n2 3 464 101 615 26 832 815 730 2.5× 1032
n3 2 289 428 8 962 809 184 930 385
2n 63 69 82
n! 20 21 24
1PFLOPS = 1015
UAL © 2021 AED: Complexidade 21 / 29
Análise de algoritmos
Complexidade
Exemplo
Análise assimptótica
Notação O
Funções de referência
Comparação entre funções
Análise de algoritmos
UAL © 2021 AED: Complexidade 22 / 29
Análise de algoritmos
Análise de algoritmos
Análise de algoritmos geralmente foca-se em dois aspetos:
• Demonstração da correção do algoritmo, de acordo com o seu objetivo;
• Demonstração da correção da sua função custo.
Existem algumas técnicas para conseguir estas demonstrações. Idealmente será possível
interpretar o algoritmo comoum modelo matemático, e demonstrar afirmações sobre ele com
recurso a métodos tradicionais, como a indução.
Por outro lado, é também possível demonstrar equivalência entre problemas, demonstrando que
os seus algoritmos solução partilham a mesma função custo.
UAL © 2021 AED: Complexidade 23 / 29
Análise de algoritmos
Correção de algoritmos
Para demonstrar a correção de um algoritmo é necessário produzir uma prova formal. Os
instrumentos que existem são os mesmo que são utilizados em demonstrações matemáticas:
produzir afirmações, e instanciar expressões lógicas com base nessas afirmações.
Nomeadamente:
• Contraexemplo: identificação de um caso em que o algoritmo não funciona, i.e., produz o
resultado errado.
• Contradição: redução ao absurdo da negação lógica da algoritmo. No entanto, a negação
lógica do algoritmo é algo difícil de determinar.
• Indução: demonstrando que o algoritmo é válido para um caso base, e para a progressão
de passos indutivos.
UAL © 2021 AED: Complexidade 24 / 29
Análise de algoritmos
Redução
Na teoria da computação, uma redução representa a transformação da descrição de um
problema noutro.
Uma redução do problema X para o problema Y implica que uma solução do problema Y é
também uma solução do problema X .
O objeto das reduções é demonstrar equivalência entre problemas, no sentido em que os dois
problemas terão a mesma função custo.
Existem várias técnicas de redução, e vários níveis de equivalência. É uma área de investigação
ativa.
UAL © 2021 AED: Complexidade 25 / 29
Análise de algoritmos
Decidibilidade
Além do tempo e espaço necessários para executar uma solução de um problema, é também
importante determinar se a solução termina para um determinado conjunto de dados de entrada.
A decidibilidade é importante para distinguir entre o cenário em que o problema tem uma
solução, mas ela é difícil de encontrar, e o cenário em que não existe solução.
Existem vários problemas em que reconhecidamente não é possível decidir.
Exemplos:
• Um algoritmo que determina se um outro algoritmo termina, é indecidível;
• O algoritmo em teste não termina, ou é exponencial?
• Um algoritmo que encontra soluções para polinómios de qualquer grau é indecidível.
• Não existem raízes, ou o grau é tão elevado que exige muito tempo?
UAL © 2021 AED: Complexidade 26 / 29
Análise de algoritmos
Determinismo
No contexto de análise de programas, determinismo representa a capacidade de decisão sobre a
correção da eventual resposta ao problema.
Assumindo duas fases para a execução de um algoritmo:
• Encontrar uma resposta para o problema
• No contradomínio do problema
• Provar que a resposta é válida
• Sim ou Não
O problema é determinista se existir um algoritmo (polinomial) que produza sempre uma
resposta (verdadeiro, ou falso) quanto à validade da solução encontrada.
UAL © 2021 AED: Complexidade 27 / 29
Análise de algoritmos
Classes de problemas
Ao criar equivalências entre problemas torna-se possível identificar classes de acordo com o custo
associado às suas soluções. A designação da classes varia de acordo com o modelo de
computação utilizado.
No entanto, geralmente são reconhecidas as seguintes, que se referem a problemas de
decidibilidade e/ou resolução:
• P, PTIME: decisão em tempo polinomial
• EXPTIME: decisão em tempo exponencial
• PSPACE: decisão em espaço polinomial
• FP: custo temporal polinomial, determinista.
• NP: custo temporal polinomial, não determinista.
• NP-Difícil: conjunto dos problemas tão ou mais difíceis que NP.
• NP-Completo: problemas NP e NP-Difícil.
UAL © 2021 AED: Complexidade 28 / 29
Análise de algoritmos
P vs NP
A conjetura mais importante que existe em teoria da computação diz que a classe de problemas
cuja verificação de solução é polinomial (P), não é equivalente à classe de problemas cuja
validação de soluções é não determinista (NP).
Este resultado é importante para determinar que existem problemas cuja solução não é possível
de encontrar em tempo polinomial, mas cuja verificação pode ser feita em tempo polinomial.
Esta conjetura oferece sustentação teórica para a criptografia.
Tratando-se ainda de uma conjetura, não tem prova encontrada.
Constitui um dos Millenium Prize Problems do Clay Mathematics Institute, com um prémio de
$1M.
UAL © 2021 AED: Complexidade 29 / 29
	Complexidade
	Exemplo
	Análise assimptótica
	Notação O
	Funções de referência
	Comparação entre funções
	Análise de algoritmos