Complexidade de algoritmos 2 (Tiberius Bonates)

Prévia do material em texto

Estruturas de Dados I – Complexidade de Algoritmos 2
Universidade Federal Rural do Semi-A´rido
Mossoro´, RN §
2011.1
1 Ana´lise de Complexidade
Em certos situac¸o˜es pra´ticas, a dimensa˜o dos dados de entrada utilizados por um programa e´ garanti-
damente limitada, isto e´, sabe-se que os dados de entrada na˜o excedem uma determinada quantidade.
Nestes casos, a decisa˜o por se adotar um ou outro algoritmo para se realizar um determinada tarefa
pode ser tomada com base no nu´mero exato de instruc¸o˜es que sera˜o realizadas por cada algoritmo.
Uma ana´lise da regia˜o de interesse dos valores para o tamanho da entrada de dados e´ tudo que se
precisa fazer. De acordo com o desempenho (dentro desta regia˜o de interesse) dos algoritmos que
esta˜o sendo avaliados, pode-se decidir por qual algoritmo se aplicar em cada parte desta regia˜o do
domı´nio.
Exemplo 1.1 Como exemplo, considere dois algoritmos, A e B, que realizam a mesma tarefa,
mas que executam nu´meros de instruc¸o˜es diferentes em seus respectivos piores casos : fA(n) =
5n2 +15n+5, fB(n) = n
3−3n2 +n+8. Substituindo-se valores de n para as func¸o˜es e´ fa´cil perceber
que, a partir do valor n = 10, o algoritmo A passa a ser mais vantajoso, pois realiza um nu´mero
total de instruc¸o˜es menor do aquele o algoritmo B. Desta forma, uma recomendac¸a˜o segura seria
utilizar o algoritmo B para valores do tamanho da entrada menores que 10, e utilizar o algoritmo A
em todos os outros casos.
Exemplo 1.2 Outro caso que ilustra esta situac¸a˜o acontece com o problema de multiplicac¸a˜o de
matrizes quadradas. O algoritmo mais simples para este tipo de tarefa exige a execuc¸a˜o de uma
quantidade de instruc¸o˜es que e´ dada por uma func¸a˜o cu´bica do tamanho da entrada, isto e´, uma
func¸a˜o do tipo f(n) = c · n3 + ..., onde c e´ uma constante inteira positiva. O algoritmo de Strassen
para multiplicac¸a˜o de matrizes e´ mais sofisticado e realiza um nu´mero total de instruc¸o˜es que e´ dado
por uma func¸a˜o polinomial em n com expoente 2.807, ou seja, uma func¸a˜o que cresce mais lentamente
do que a do algoritmo mais simples. No entanto, para valores pequenos de n, os demais termos da
func¸a˜o que expressa o nu´mero de instruc¸o˜es realizadas pelo algoritmo de Strassen representam um
custo computacional que, juntamente com o termo de expoente 2.807, acaba superando o nu´mero de
instruc¸o˜es executadas pelo algoritmo simples. Apenas para matrizes com dimensa˜o maior que 100,
o algoritmo de Strassen passa a valer a pena.
2 Complexidade Assinto´tica
O conceito de complexidade assinto´tica de um algoritmo diz respeito ao crescimento, a longo prazo,
da func¸a˜o que descreve o nu´mero de instruc¸o˜es executadas pelo algoritmo. Isto e´, se um algoritmo A
§Tibe´rius O. Bonates, tbonates@ufersa.edu.br.
1
realiza um nu´mero de instruc¸o˜es que e´ descrito pela func¸a˜o f(n), onde n e´ o tamanho da entrada do
algoritmo, estamos interessados na taxa (ou velocidade) de crescimento da func¸a˜o f(n), na medida
em que n aumenta.
O comportamento assinto´tico de uma func¸a˜o e´ o crite´rio utilizado na pra´tica para se comparar o
desempenho de dois ou mais algoritmoa para uma determinada tarefa. Conforme veremos, este tipo
de ana´lise nos permite comparar objetivamente algoritmos com base no seu desempenho aproximado
a` medida em que os dados fornecidos como entrada crescem em tamanho.
Com este intuito, iremos tipicamente ignorar os termos da func¸a˜o que tem menor influeˆncia em
seu crescimento, isto e´, os termos de menor ordem. Iremos tambe´m ignorar quaisquer constantes
multiplicativas dos termos de maior ordem. Desta forma, obtemos um perfil simplificado da func¸a˜o,
e podemos comparar, de forma razoa´vel, a ordem de crescimento de duas ou mais func¸o˜es a` medida
que n cresce, sem levar em conta flutuac¸o˜es locais em regio˜es espec´ıficas do domı´nio da func¸a˜o.
Procedendo desta forma, e´ poss´ıvel dizer que, no pior caso, um dado algoritmo C ira´ realizar
“pelo menos”, ou “no ma´ximo”, ou ainda “aproximadamente”, uma quantidade de instruc¸o˜es que
apresenta certa ordem de crescimento, na medida em que n cresce. As notac¸o˜es apresentadas nas
seguintes sec¸o˜es introduzem a formalidade utilizada para se fazer estas afirmac¸o˜es.
3 Notac¸a˜o O
Dizemos que f(n) e´ O(g(n)) se
∃ c ∈ <+, n0 ∈ Z+ tais que 0 ≤ f(n) ≤ c · g(n), ∀n ≥ n0.
Em outras palavras, a partir de certo valor n0 para o tamanho da entrada de dados, a func¸a˜o g
passa a “dominar” a func¸a˜o f , crescendo mais ra´pido do que f de maneira consistente.
Exemplo 3.1 Exemplos de uso da notac¸a˜o O:
• 3n+ 5 e´ O(n)
• 100n+ 5000 e´ O(n)
• 3n+ 5 e´ O(n2)
• n3 + 10n2 − 6 e´ O(n3)
• (n+ 1)(10 + log2(n)) e´ O(n log2(n))
4 Notac¸a˜o Ω
Dizemos que f(n) e´ Ω(g(n)) se
∃ c ∈ <+, n0 ∈ Z+ tais que 0 ≤ c · g(n) ≤ f(n), ∀n ≥ n0.
Isto e´, f cresce mais rapidamente que g a partir de certo tamanho da entrada.
Exemplo 4.1 Exemplos de uso da notac¸a˜o Ω:
• 3n+ 5 e´ Ω(n)
2
• 100n+ 5000 e´ Ω(n)
• n2 + 5n e´ Ω(n2)
• n2 + 5n e´ Ω(n)
• 3n log2(n) + 7n+ 10 e´ Ω(n log2(n))
5 Notac¸a˜o Θ
Em certos casos, temos uma func¸a˜o f(n) que e´ O(g(n) e Ω(g(n)), simultaneamente. E´ conveniente
definir uma notac¸a˜o simplificada para este caso. Dizemos, portanto, que f(n) e´ Θ(g(n)) se
∃ c1, c2 ∈ <+, n0 ∈ Z+ tais que 0 ≤ c1 · g(n) ≤ f(n) ≤ c2 · g(n), ∀n ≥ n0.
Neste caso, a func¸a˜o f cresce a` mesma taxa de crescimento que a func¸a˜o g.
Como exemplo de uma relac¸a˜o deste tipo, considere a tarefa de se encontrar o menor elemento
de um vetor na˜o-ordenado de inteiros. O algoritmo mais natural mais se realizar esta tarefa consiste
em examinar todo o vetor, mantendo-se sempre a informac¸a˜o acerca do menor elemento examinado
ate´ o presente momento.
Uma ana´lise do nu´mero de instrucoes executadas por este algoritmo, que chamaremos de fA(n),
revela que na˜o ha´, de fato, uma entrada de dados que resulte em um nu´mero de instruc¸o˜es inferior
a`quele necessa´rio para se processar qualquer outra entrada. Desta forma, temos que o nu´mero de
operac¸o˜es do algoritmo sera´, necessariamente, da mesma ordem de grandeza do tamanho da entrada,
independente do tamanho da entrada. Em outras palavras, o algoritmo ira´ inspecionar todos os n
elementos do vetor, quaisquer que sejam seus valores, resultando na conclusa˜o de que fA(n) e´ Ω(n)
e, tambe´m, O(n). Portanto, a complexidade assinto´tica deste algoritmo e´ Θ(n).
6 Algoritmos O´timos
Para a maioria das tarefas computacionais, e´ possivel se determinar uma estimativa, mesmo que
grosseira, a respeito do numero minimo de instrucoes que e´ preciso se executar para concluir a
tarefa. Considere, por exemplo, o caso do algoritmo discutido acima para o caso de se encontrar
o menor elemento de um vetor na˜o-ordenado. Sabemos que qualquer algoritmo que se proponha a
realizar tal tarefa precisa inspecionar todos os elementos do vetor. Ou seja, qualquer algoritmo que
conclua a tarefa precisa executar uma quantidade mı´nima de n operac¸o˜es, de onde podemos concluir
que qualquer algoritmo que conclua a tarefa e´ Ω(n). Perceba que esta e´ uma caracter´ıstica teo´rica,
que e´ intr´ınseca ao problema ou tarefa em si, e na˜o a um algoritmo em particular.
O nu´mero de instruc¸o˜es realizadas pelo algoritmo que percorre o vetor sequencialmente, atua-
lizando a informac¸a˜o do menor elemento visto ate´ o momento, e´ O(n). Desta forma, o algoritmo
alcanc¸a uma complexidade de pior caso que possui a mesma ordem de crescimento do limite teo´rico
do problema a que se propo˜e resolver. Em tais situac¸o˜es dizemos que o algoritmo em questa˜o e´
o´timo. A implicac¸a˜o pra´tica deste fato e´ que nenhum algoritmo para resolver a mesma tarefa tera´
desempenho muito melhor (em termos assinto´ticos) do que o algoritmo em questa˜o.
3
7 Algoritmos Eficientes
Um algoritmo e´ dito eficiente se sua complexidade de pior caso e´ O(g), onde g e´ uma func¸a˜opoli-
nomial. Todos os algoritmos estudados neste texto, por exemplo, podem ser ditos eficientes. Por
outro lado, um algoritmo com complexidade O(2n) na˜o e´ eficiente.
Com base nesta definic¸a˜o, podemos classificar tarefas computcionais, ou problemas computa-
cionais, nas categorias de problemas trata´veis e intrata´veis. Um problema e´ dito tratav´el se ele
admite um algoritmo eficiente que o resolva. Por outro lado, um problema para o qual na˜o se
conhece nenhum algoritmo eficiente que o resolva e´ chamado de problema intrata´vel.
8 Exerc´ıcios
1. Escrever uma func¸a˜o que recebe um vetor ordenado de inteiros, um inteiro informando o
tamanho n do vetor, e um valor inteiro que se deseja encontrar dentro do vetor. A func¸a˜o deve
retornar a posic¸a˜o (´ındice) do elemento procurado, ou o valor -1, caso o elemento na˜o exista
no vetor. Determinar a complexidade de pior caso de seu algoritmo utilizando a notac¸a˜o O.
2. Propor um algoritmo para somar duas matrizes quadradas de dimensa˜o n. Fornecer a com-
plexidade do algoritmo utilizando a notac¸a˜o Ω.
3. Utilizando a notac¸a˜o de complexidade O, explicar porque a func¸a˜o f(n) = 4n+ 3 e´ O(n).
4. Se f(n) = (3n6 + 5n2 − 6)(n+ log n), enta˜o f e´ O(n6 log n)? Explicar sua resposta.
5. Apresentar um algoritmo o´timo para o problema de se encontrar os dois maiores valores em
um vetor na˜o-ordenado de inteiros. Explicar porque o algoritmo e´ o´timo.
4