3 complexidade

Prévia do material em texto

Estrutura de Dados
03 - Complexidade
Manoel Vilela
<2017-08-29 Tue 21:37>
Sumário
1 Descrição 1
2 Notações 1
2.1 Big-O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Big-Omega . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Big-Theta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 Casos 3
3.1 Pior caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.2 Melhor caso . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.3 Caso médio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
4 Classes de complexidades 4
5 Análises 4
5.1 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
6 P vs NP 5
7 Referências 5
1 Descrição
No final da aula de hoje foi dada uma intuição sobre o que é complexidade
de algoritmo e porque sua importância em análise para caracterizar o tempo
de execução de diferentes classes tipos de algoritmos.
1
Durante a exposição do tema, o professor representou a análise através da
dissecção do algoritmo de ordenação por inserção, também conhecido como
Insertion Sort. Como bem se sabe, o que caracteriza a solução assintótica
de uma complexidade é seu polinômio de maior grau ou entidade de maior
complexidade usando a notação Big-O. Dizemos que Big-O é uma limitação
por cima (upper bound) do comportamento de uma função.
Dessa maneiraq, por exemplo um algoritmo O(n) possuí complexidade
linear (acesso em uma lista encadeada), O(n2) possui complexidade quadrá-
tica (Insertion Sort pior caso) e O(nlog2(n)) possui complexidade logarít-
mica (Merge Sort pior caso).
2 Notações
As notações para descrever complexidade são construtores de conjuntos
que agrupam todas possíveis funções características para algoritmos indepen-
dente dos coeficientes constantes referente a máquina, custo de operações do
algoritmo ou operações de inicialização.
Dessa maneira, pode-se analisar um algoritmo de maneira agnóstica sobre
o hardware que ele é executado. Há três notações muito comum na literatura
para descrever complexidade de algoritmos: O, Ω e Θ. Existem as versões
para little dessas três, mas por não ser muito utilizado, só falarei sobre a
notação big.
2.1 Big-O
A notação Big-O, uma das mais utilizadas pra descrever algoritmos,
refere-se a função assintótica com limite superior (upper bound). Por exem-
plo, o algoritmo Insertion Sort possui complexidade O(n2). Isso quer dizer
que para todas possíveis funções da classe quadrática, nenhuma é maior que
Ø(n2\), pois esse é o limite superior. Importante destacar que todas essas
notações geram um conjunto de funções. (Sim, é um conjunto!)
A definição dessa notação é feita da seguinte maneira:
O(f(n)) = {T (n) | c, n ∈ R∗+ 0 ≤ T (n) ≤ cf(n)
for n ≥ a
where T (a) = cf(a)}
(1)
Uma possível leitura dessa notação é: ‘Este algoritmo não leva mais
tempo que O(f(n))’.
2
2.2 Big-Omega
A notação Big-Omega, utilizada não tão quanto a Big-O, descreve um
conjunto de funções delimitadas por um limite inferior (lower bound). Muitas
vezes usada para descrever o melhor caso de um algoritmo, possui a seguinte
definição:
Ω(f(n)) = {T (n) | c, n ∈ R∗+ 0 ≤ cf(n) ≤ cT (n)
for n ≥ a
where T (a) = cf(a)}
(2)
Uma possível leitura dessa notação é: ’Este algoritmo leva ao menos o
tempo de Ω(f(n))’.
2.3 Big-Theta
Por outro lado, anotação Big-Theta, referencia a um limite superior e
inferior, isto é, como um sanduíche. Em inglês referenciando como tight
bound. É importante não relacionar essa notação com caso médio, pois o
que essa notação nos diz é que o algoritmo se comporta numa determinada
faixa, mas não que esse seja o caso médio.
A definição dessa notação é similar as duas anteriores, misturando um
pouco de cada definição 1:
Ω(f(n)) = {T (n) | c1, c2, n ∈ R∗+ 0 ≤ c1f(n) ≤ T (n) ≤ c2f(n)
for n ≥ a
where T (a) = c1f(a) ≤ c2f(a)}
(3)
Uma possível leitura dessa notação é: ’Este algoritmo leva o tempo na
ordem de Θ(f(n))’. 2
3 Casos
Um algoritmo pode ter diferentes comportamentos e complexidades para
um tipo de entrada. É o que conhecemos sobre: pior caso, melhor caso e
1Ainda estou com dúvida como analisar esse a da definição, pois é o ponto de estabili-
dade entre as funções, mas como agora determinar sendo ele uma possível intersecção do
ponto estável de três funções?
2Para a notação Theta ser usada, a função deve ter O(f(n)) e Ω(f(n) definido. Ou
seja, ela deve ser limitada fortemente tanto por baixo quanto por cima. Se um algoritmo
leva ao menos X(n) e não mais que Y(n), mas se X(n) = Y (n) então esse algoritmo
simplesmente leva Θ(X(n)) pra completar.
3
caso médio. Todas as notações podem ser utilizadas em cada caso.
3.1 Pior caso
O pior caso se refere quando o algoritmo levar o maior tempo para ter-
minar. É denotado geralmente com a notação Big-O pois refere-se ao limite
superior assintótico da função (como o algoritmo se comporta para entradas
muito grandes). Observar no entanto que as outras notações também podem
ser usadas para analisar esse caso.
3.2 Melhor caso
O melhor caso se refere quando o algoritmo levar o menor tempo possível
para terminar, com uma complexidade diferente. Alguns autores se referem
a notação Omega para o estudo de melhor caso, no entanto isso não é res-
tritamente necessário. A notação omega oferece o limite inferior assintótico
de uma função, como ela se comporta para entradas muito pequenas e sua
complexidade. A distribuição de melhor caso não é diretamente relacionada
ao tamanho da entrada, mas sim com sua distribuição 3. Tal como para
alguns algoritmos de ordenação o melhor caso se refere a entrada já estiver
ordenada.
3.3 Caso médio
Não existe uma notação específica e, por favor, não confunde com a
notação Big-Theta. Para sua análise é geralmente feito um modelo proba-
bilístico a partir da experimentação de muitas entradas, observando qual
tiver a probabilidade maior de ser na média de o algoritmo comportar-se de
uma determinada maneira. Devido sua inconveniência, muitos algoritmos
não possuem de fato um caso médio analisado (falta de dados).
4 Classes de complexidades
Classes de complexidade podem ser ordenadas da seguinte maneira:
O(1) < O(log(n)) < O(n) < O(nlog(n))
< O(n2) < O(n3) < O(2n) < O(n!)
(4)
3carece fonte. O professor sempre se refere a Ω como melhor caso, no entanto na
internet vejo outras definições. preciso tirar minha dúvida com isso lendo os livros.
4
5 Análises
Nas próximas seções irei elucidar como é feito a análise de alguns algo-
ritmos de ordenação, tal como na sua implicação no tempo de execução.
5.1 Insertion Sort
Figura 1: Exemplo de análise do algoritmo de ordenação por inserção.
Melhor caso: Ω(n) Pior caso: O(n2)
A análise de um algoritmo é feito através dos seus coeficientes constantes
que relaciona um tipo de operação e a quantidade de operações que são feitas.
No geral é simplesmente isso. Laços de iterações são vistos como loops e
muitas vezes eles que possuem a maior complexidade assintótica, como nesse
caso. Para o melhor caso o segundo laço nunca ocorre, então é encarado
como apenas um laço. Mas para o pior caso isso não é verdade, necessitando
dois laços aninhados, o que causa um comportamento quadrático.
6 P vs NP
Um grande problema da matemática que ainda não foi resolvido. O
problema se refere se há qualquer solução polinomial para um problema
que não seja P, isto é, seja NP. P significa polinomial, NP significa tempo
5
polinomial não-determinístico, ou em inglês non-deterministic polynomial
time.
É premiado como um dos 7 problemas do Prémio Millenium. Sua solução
além de todo o crédito provavelmente até o término da humanidade, receberá
um prêmio de 1 milhão de dólares.
Muitos matemáticos e cientistas da computação acreditam que a resposta
do problema seja P ! = NP . Isto é, de fato não é possível encontrar uma
solução polinomialpara problemas que sejam de fato NP. Um fator para se
acreditar nisso é que nenhum algoritmo polinomial para problemas NP foi
encontrado até hoje.
7 Referências
• THOMAS CORMEN, 2012, Algoritmos: Teoria e prática 2ª edição.
6
	Descrição
	Notações
	Big-O
	Big-Omega
	Big-Theta
	Casos
	Pior caso
	Melhor caso
	Caso médio
	Classes de complexidades
	Análises
	Insertion Sort
	P vs NP
	Referências