TC1-complexidade

Prévia do material em texto

Algoritmos
Um algoritmo é um procedimento, consistindo de um conjunto de regras não ambíguas, as quais especificam, para cada entrada, uma seqüência finita de operações, terminando com uma saída correspondente.
Um algoritmo resolve um problema quando, para qualquer entrada, produz uma resposta correta, se forem concedidos tempo e memória suficientes para sua execução.
1
Limitações 
Os recursos de espaço e tempo requeridos têm grande importância em casos práticos.
Às vezes, o algoritmo mais imediato está longe de ser razoável em termos de eficiência.
2
Complexidade de algoritmos
A complexidade de um algoritmo é o reflexo do esforço computacional requerido para executá-lo. 
Esforço computacional mede a quantidade de trabalho, em termos de tempo de execução ou da quantidade de memória requerida.
Existem vários critérios de avaliação de um algoritmo como:
- quantidade de trabalho requerido,
- quantidade de espaço requerido,
- simplicidade,
- exatidão de resposta 
3
Medidas de Complexidade
Introduz as idéias de complexidade pessimista (pior caso), do melhor caso e complexidade média;
Ordens Assintóticas
Introduz as idéias de comportamento assintótico (notações Ο, o, Ω,  e Θ), e examinam-se algumas de suas propriedades.
4
Existem vários aspectos a considerar na determinação da complexidade de um algoritmo. Um critério pode ser medir o tempo de execução, mas:
- Uma pequena mudança no programa pode não representar uma mudança significativa no algoritmo, mas, apesar disso, a velocidade de execução pode ser afetada.
- Além disso, se dois programas são comparados, primeiro numa máquina, depois em outra, as comparações podem dar resultados diferentes.
- Este critério é fortemente dependente tanto da implementação quanto da máquina.
Uma alternativa útil é uma análise matemática das dificuldades intrínsecas da resolução do problema computacionalmente.
5
Critérios de Complexidade
Para medir a quantidade de trabalho realizado por um algoritmo, é escolhida uma operação, chamada operação fundamental. Às vezes, é necessária mais de uma operação fundamental, talvez com pesos diferentes: custo.
Exemplo: em um algoritmo de ordenação, uma operação fundamental natural é a comparação entre elementos e a movimentação desses elementos.
6
Tamanho da entrada de dados
Exemplos:
- para matrizes quadradas: ordem de d.
- para listas: comprimento da lista.
- para um grafo: números n de vértices e m de arestas.
- para números: a quantidade de caracteres (como bits) usada para codificá-los.
O objetivo é associar um custo a cada tamanho de entrada, ao invés de a cada entrada.
Além disso, um algoritmo pode apresentar desempenhos distintos sobre várias entradas, apesar de elas terem o mesmo tamanho.
Qual devemos escolher?
Aqui entrarão os critérios de complexidade, como o do pior caso, melhor caso e o do caso médio.
7
Complexidade Média
A complexidade média (ou esperada) de um algoritmo é o valor médio de seus desempenhos sobre todas as entradas com tamanho n, usando-se como peso a probabilidade de ocorrência de cada entrada.
Complexidade Pessimista
A complexidade pessimista de um algoritmo fornece seu desempenho no pior caso: o pior desempenho que se pode esperar sobre todas as entradas com tamanho n.
8
Exemplo : Busca Seqüencial
9
Tomemos como operação fundamental a comparação = (no se da linha 4) e como tamanho da entrada o tamanho n de tab.
Se ch encontra-se:
- na 1a posição, Busca_Seq faz 1 comparação
- na 2a posição, Busca_Seq faz 2 comparações
. . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . .
- na ka posição, Busca_Seq faz k comparações
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
-na na posição (ou não está em tab), Busca_Seq faz n comparações.
Assim, a complexidade no pior caso é n (linear no tamanho n da entrada).
Se todos os elementos da tabela forem igualmente prováveis como chave, então o número médio de comparações será:
10
Comparação entre complexidades
Um problema pode ter mais de um algoritmo para resolvê-lo. Qual deles escolher?
Fixada as operações fundamentais e função tamanho, a cada algoritmo a ∈ A temos o seu custo.
Consideremos um conjunto A de algoritmos para um dado problema Π. 
Freqüentemente, interessa-nos identificar um algoritmo ótimo. 
Essas idéias envolvem comparações entre funções f e g de IN em IN (medem custo de um algoritmo) . Quando f é “melhor” do que g?
Há vários critérios; os mais usados baseiam-se em comportamento assintótico
(para entradas de tamanho grande).
11
Ordens Assintóticas
A complexidade assintótica é definida pelo crescimento da complexidade para entradas suficientemente grandes.
Algoritmo assintoticamente mais eficiente é melhor para todas as entradas (grandes), exceto para entradas relativamente pequenas.
A complexidade exata costuma conter muita informação, resultando em uma função de difícil análise e manipulação, vamos simplificar.
Exemplo:
f(n) = 4n + 5 → 4n → n
Em geral quando o volume de dados é pequeno a complexidade não é limitadora, para grande volume de dados é que torna-se essencial.
12
Notação Ο
A notação Ο define uma cota assintótica superior.
Define-se que f(n) é Ο(g(n)) sse:
13
A notação O é usada para expressar o limite superior do tempo de execução de cada algoritmo para resolver um problema específico (limite superior de cada algoritmo para um problema).
Exemplo:
Um limite superior de um algoritmo de ordenação que utiliza comparação entre elementos é O(n2).
 Ex: BubleSort e QuickSort
Outro limite superior de um algoritmo de ordenação que utiliza comparação entre elementos é O(nlogn).
 Ex: MergeSort
14
Propriedades:
f(n) = O(f(n))
c .O(f(n)) = O(f(n)) c constante
O(f(n)) + O(f(n)) = O(f(n))
O( O(f(n)) ) = O(f(n))
O(f(n)) + O(g(n)) = O( max(f(n),g(n)) )
O(f(n))O(g(n)) = O(f(n)g(n))
f(n)O(g(n)) = O(f(n)g(n))
15
Exemplos
1) Suponha 3 trechos de programas cujos tempos de execução sejam O(n), O(n2) e O(nlogn).
O tempo de execução dos 2 primeiros trechos é O(max(n,n2), que é O(n2).
O tempo de execução de todos os 3 trechos é, então, O(max(n2, nlogn)), que é O(n2)
16
2) 
Procedure Verifica_Item_Lista
			(Lista: TipoLista; x: TipoItem; pos: integer);
Var i: integer;
Begin
	i:=1;
	achou := false;
	while (i <= Lista.Tamanho) and not achou do begin
		inc(i);
		if Lista.Item[i] = x then
			achou := true;
	end;
	if achou then
		pos := i
	else
		pos := -1;
O(1)
O(N)
f(N) = O( O(1) + O(N) + O(?)) = 
O(?)
O(?)
17
Exercícios:
Indique se as alternativas abaixo são V ou F:
1 - 3n3 +2n2 + 100n= O(n3)
2 - n = O(n3)
3 - n3 + 200= O(n2)
4 - logn = O(n)
5 - nlogn3 = O(n)
6 - nlog23 = O(n)
7 - n! = O(nn)
8 - 22n = O(2n)
9 - 2n+1 = O(2n)
10 - logn + 1/n + 3 = O(logn)
18
Notação o
Dizemos f(n) = o(g(n)), se para qualquer constante positiva c, existe uma constante n0 > 0 tal que 
 0  f(n) < cg(n)  n  n0.
EX: 2n2  o(n2)
 2n = o(n2) 
19
Notação Ω
A notação Ω define uma cota assintótica inferior.
Define-se que f(n) é Ω (g(n)) sse:
20
Notação Θ
A notação Θ define um limite assintótico exato.
Define-se que f(n) é Θ (g(n)) sse:
Note que a ordem Θ é um caso particular das ordens Ο e Ω, isto é, se f(n) é Θ(g(n)), então f(n) também é Ο(g(n)) e Ω (g(n)).
21
Algumas classes de comportamento assintótico
Complexidades mais comuns
O(1)
A complexidade é constante, ou seja, o tempo (espaço) é independente da quantidade da entrada.
O(logn)
ComplexidadeLogaritmica
O(n)
Complexidade Linear
O(nlogn)
Complexidade “nlogn”
O(n2)
Complexidade Quadrática
O(n3)
Complexidade Cúbica
O(2n)
Complexidade Exponencial
O(n!)
Complexidade Fatorial
22
Relação entre as Ordens
 
23
Classes de Comportamento Assintótico
f (n) = O(1) (complexidade constante)
O uso do algoritmo independe do tamanho de n.
Neste caso as instruções do algoritmo são executadas um número fixo de vezes.
24
f(n) = O(log n) (complexidade logarítmica)
Ocorre tipicamente em algoritmos que resolvem um problema transformando‑o em problemas menores.
Exemplo: Busca bináriaQuando n é mil e a base do logaritmo é 2, log2 n  10
Quando n é um milhão, log2 n  20.
25
f(n)= O(n) (complexidade de linear)
Em geral um pequeno trabalho é realizado sobre cada elemento de entrada.
Esta é a melhor situação possível para um algoritmo que tem que processar n elementos de entrada ou produzir n elementos de saída.
Cada vez que n dobra de tamanho o tempo de execução dobra.
26
f(n)= O(nlogn)
Este tempo de execução ocorre tipicamente em algoritmos que resolvem um problema quebrando‑o em problemas menores, resolvendo cada um deles independentemente e depois ajuntando as soluções.
Exemplos : heapsort, mergesort
Quando n é um milhão e a base do logaritmo é 2, nlog2 n é cerca de 20 milhões.
Quando n é dois milhões, n log2n é cerca de 42 milhões, pouco mais que o dobro.
27
f(n)= O(n2) (complexidade quadrática)
Algoritmos desta ordem de complexidade ocorrem quando os itens de dados são processados aos pares, muitas vezes em um loop dentro de outro.
Exemplos: Inserção, bolha
Quando n = 1000, o número de operações é da ordem de 1 milhão.
Sempre que n dobra , o tempo de execução é multiplicado por 4. Algoritmos deste tipo são úteis para resolver problemas de tamanhos relativamente pequenos.
28
f(n)= O(n3) (complexidade cúbica)
Algoritmos desta ordem de complexidade são úteis apenas para resolver pequenos problemas.
Exemplo: multiplicação de matrizes (clássica)
Quando n = 100, o número de operações é da ordem de 1 milhão.
Sempre que n dobra o tempo de execução fica multiplicado por 8.
29
f(n)= O(2n) (complexidade exponencial)
Algoritmos desta ordem de complexidade geralmente não são úteis sob o ponto de vista prático. Eles ocorrem na solução de problemas quando se usa força bruta para resolvê‑los.
Quando n = 20, o tempo de execução é cerca de um milhão.
Quando n dobra, o tempo de execução fica elevado ao quadrado.
30
Importância da complexidade de algoritmos
Compara o desempenho de dois algoritmos que calculam o determinante de uma matriz nxn, considerando tempos de operações de um computador real.
O crescente avanço tecnológico, permitindo a criação de máquinas cada vez mais rápidas, pode parecer ofuscar a importância da complexidade de tempo de um algoritmo.
31
Ilustra o impacto de um aumento de velocidade de operação sobre alguns algoritmos, considerando uma segunda máquina dez vezes mais rápida que a primeira.
Note que a melhora é muito boa para algoritmos rápidos e insignificante para algoritmos lentos.
32
Supondo-se que um computador execute uma operação em 1μs, a tabela a seguir descreve os tamanhos limites de problemas resolvíveis por algoritmos de diferentes complexidades em 1 segundo, 1 minuto e 1 hora
A partir das tabelas anteriores é possível concluir que a capacidade de um algoritmo é função de sua complexidade.
33