Complexidade de algoritmos 1 (Tiberius Bonates)

Prévia do material em texto

Estruturas de Dados I – Complexidade de Algoritmos
Universidade Federal Rural do Semi-A´rido
Mossoro´, RN §
2011.1
1 Introduc¸a˜o
Considere o problema de encontrar um valor negativo em um vetor de inteiros. O que se pode dizer
sobre o nu´mero de instruc¸o˜es necessa´rio para se encontrar um valor negativo dentro de um vetor
contendo n valores inteiros? De maneira mais geral, o que se pode dizer sobre o nu´mero total de
instruc¸o˜es que um determinado algoritmo executa?
No caso problema de se encontrar um valor negativo dentro de um vetor, podemos imaginar um
algoritmo simples que percorre o vetor sequencialmente, a partir da primeira posic¸a˜o, e interrompe
sua execuc¸a˜o assim que um valor negativo e´ encontrado. Vamos chamar este algoritmo de Algoritmo
A e consideremos a seguinte implementacao para A:
#define N 10
int v[N];
int algoritmoA() {
for (int i=0; i<N; i++)
if (v[i] < 0)
return i;
return 0;
}
A seguir, analisaremos este algoritmo em detalhe, considerando o nu´mero total de instruc¸o˜es
que sera˜o executadas por ele. Para o propo´sito deste tipo de ana´lise, iremos contabilizr o nu´mero
total de instruc¸o˜es individuais dos seguintes tipos: comandos de atribuic¸a˜o, incremento/decremento
e comparac¸a˜o.
2 Melhor e Pior Casos
E´ poss´ıvel que o primeiro elemento do vetor seja negativo, o que resultaria em apenas uma iterac¸a˜o
do lac¸o principal do algoritmo. Ao todo, o algoritmo executaria um total de 4 instruc¸o˜es: uma
inicializac¸a˜o (da varia´vel i), uma comparac¸a˜o (i<N), uma comparac¸a˜o (v[i]<0) e a instruc¸a˜o de
retorno.
§Tibe´rius O. Bonates, tbonates@ufersa.edu.br.
1
Obviamente, nem sempre teremos um valor negativo na primeira posic¸a˜o do vetor. Na verdade,
este caso descreve uma situac¸a˜o “otimista”, isto e´, um cena´rio no qual o algoritmo executa o menor
nu´mero poss´ıvel de instruc¸o˜es. Este cena´rio e´ chamado de “melhor caso”. Os outros casos poss´ıveis
sa˜o: (i) apenas o u´ltimo elemento do vetor e´ negativo; (ii) o vetor na˜o conte´m elementos negativos;
e (iii) existe pelo menos um elemento negativo, mas este na˜o se encontra na primeira nem na u´ltima
posic¸a˜o do vetor. Desta forma, dependendo dos dados de entrada (valores no vetor v), um mesmo
algoritmo A, pode executar nu´meros diferentes de instruc¸o˜es.
E´ poss´ıvel, conforme veremos, fornecer algumas garantias com relac¸a˜o ao nu´mero mı´nimo, ao
nu´mero ma´ximo, e ate´ mesmo ao nu´mero me´dio, de instruc¸o˜es que A executa.
Exemplo 2.1 Questa˜o: Determinar os nu´meros de instruc¸o˜es que sera˜o executadas pelo algoritmo
A para encontrar um valor negativo nos seguintes vetores. Iremos assumir que o vetor v foi dimen-
sionado apropriadamente para cada um dos casos abaixo; isto e´, sua declarac¸a˜o foi feita utilizando-se
o tamanho correto (valor N) do vetor em cada caso: 4, 9, 4, 5 e 6, respectivamente.
[−9, 4,−2, 19]
[−6, 1, 2, 3, 4, 5, 6, 7, 8]
[1, 5, 32, 4]
[3, 2, 7, 12, 6]
[1, 2, 3, 4, 5, 1]
Os dois primeiros vetores possuem a primeira componente negativa. Desta forma, em ambos os
casos, teremos apenas 4 instruc¸o˜es executadas, conforme discussa˜o acima a respeito do melhor caso.
Isto nos leva a` observac¸a˜o de que o nu´mero de instruc¸o˜es no melhor caso independe do tamanho do
vetor.
Os demais vetores ilustram o que chamamos de “pior caso”, que corresponde aos cena´rios em
que o algoritmo executaria a maior quantidade de passos poss´ıvel ate´ concluir sua execuc¸a˜o. Para o
terceiro vetor, o algoritmo A executa um total de 13 instruc¸o˜es, conforme discriminado abaixo:
• inicializac¸a˜o: i=0;
• 5 comparac¸o˜es do for: i<N, para i assumindo os valores 0, 1, 2 e 3;
• 4 comparac¸o˜es do if: v[i]<0, para i assumindo os valores 0, 1, 2 e 3;
• 4 incrementos do for: i++, para i assumindo os valores 0, 1 e 2;
• retorno.
Perceba que o nu´mero de instruc¸o˜es de comparac¸a˜o coincide com o dobro do tamanho do vetor,
mais um. Ale´m disso, o nu´mero de instruc¸o˜es de incremento coincide com o tamanho do vetor. Isto
na˜o acontece por acaso: como estamos lidando com o pior caso, iremos necessariamente percorrer
todo o vetor, o que resulta em exatamente N+1 comparac¸o˜es do tipo i<N (uma comparac¸a˜o antes do
in´ıcio de cada iterac¸a˜o do lac¸o for, e uma ao final da u´ltima iterac¸a˜o, imediatamente antes do lac¸o
ser finalizado), N comparac¸o˜es do tipo v[i]<0, e N incrementos do tipo i++.
Como os outros dois vetores, de tamanhos 5 e 6, respectivamente, tambe´m correspondem ao pior
caso do algoritmo, a execuc¸a˜o de A seguira´ o mesmo comportamento descrito acima. Desta forma,
2
teremos um total de 1 + 6 + 5 + 5 + 1 = 18 instruc¸o˜es realizadas pelo algoritmo ao lidar com o
penu´ltimo vetor e um total de 1 + 7 + 6 + 6 + 1 = 21 instruc¸o˜es para o u´ltimo vetor. E´ fa´cil perceber
(e tambe´m provar, por induc¸a˜o) que o nu´mero de operac¸o˜es a serem executadas pelo algoritmo A,
no pior caso, e´ dado pela expressa˜o 1 + (n+ 1) + 2n+ 1 = 3n+ 3, onde a varia´vel n corresponde ao
valor de N no co´digo.
E´ importante perceber que, embora o pior caso para o algoritmo A exija um nu´mero constante
de instruc¸o˜es (independendente do tamanho total do vetor) isto na˜o e´ sempre verdade. Conforme
veremos adiante, o melhor caso para certos algoritmos de ordenac¸a˜o de vetores requer a execuc¸a˜o
de uma quantidade de instruc¸o˜es proporcional ao tamanho do vetor. Podemos ver este tipo de
comportamento no pior caso do algoritmo A, no qual o nu´mero de instruc¸o˜es executadas no pior
caso e´ uma func¸a˜o do numero total de elementos do vetor.
3 Melhorando o Pior Caso
Em certos casos, e´ poss´ıvel se modificar um algoritmo para que ele apresente um melhor desem-
penho de pior caso. Muitas vezes e´ poss´ıvel, tambe´m, preprocessar os dados, ou organiza´-los de uma
maneira diferente, de forma a melhorar o desempenho de um determinado algoritmo. Apesar disto,
existem limites inferiores que para o nu´mero de instruc¸o˜es necessa´rias para se realizar certas tarefas.
No caso da tarefa de se encontrar um elemento negativo em um vetor arbitra´rio, e´ fa´cil perceber
que, para qualquer algoritmo que se imagine, havera´ sempre um pior caso no qual sera´ necessa´rio
avaliar pelo menos uma vez cada elemento do vetor. Ou seja, o nu´mero de instruc¸o˜es no pior caso e´
pelo menos N, o tamanho do vetor.
Considere a tarefa realizada pelo algoritmo A. Abaixo, mostraremos um algoritmo levemente
modificado, que atinge um melhor desempenho de pior caso. Primeiro, ao alocarmos memo´ria para
armazenar o vetor v, iremos requisitar uma posic¸a˜o adicional para v, isto e´, v tera´ N+1 posic¸o˜es.
Trataremos esta posic¸a˜o adicional como sendo uma posic¸a˜o ao final do vetor, a ser preenchida com
um valor negativo. Este valor na˜o faz parte dos dados de entrada, mas sera´ essencial para a modi-
ficac¸a˜o que faremos no algoritmo A.
Ja´ que temos agora a garantia de que o vetor aumentado v contera´ um valor negativo, pode-
mos rescrever o algoritmo com a peculiaridade na˜o checarmos se ja´ atingimos o final do vetor sem
encontrar nenhum valor negativo. Afinal, temos a garantia de que, mesmo que os dados reais de
v na˜o incluam nenhum valor negativo, a entrada v[N] conte´m, garantidamente, um valor negativo.
Esta entrada adicional do vetor e´ normalmente chamada de valor sentinela, pois e´ um valor que esta´
presente apenas para garantir o te´rmino do algoritmo de maneira segura. O co´digo modificado pode
ser escrito na forma do seguinte algoritmo B:
#define N 10
int v[N+1];
v[N] = -1; // preencher ultima posicao com valor negativo
int algoritmoB() {
int i=0;
while (v[i] >= 0) i++;
return v[i];
}
3
Fazendo o mesmo tipo de contagem de execuc¸o˜es do pior caso que fizemos para o algoritmo A,
obtemos os seguintes valores para B: uma instruc¸a˜o de atribuic¸a˜o (i=0), uma instruc¸a˜o de retorno,
N incrementos, e N+1 comparac¸o˜es do tipov[i] >= 0 (uma para cada posic¸a˜o do vetor v, incluindo
a u´ltima posic¸a˜o, para a qual o teste ira´ falhar). Se levarmos em conta tambe´m a instruc¸a˜o v[N]=-1,
temos um total de 2n+ 4 instruc¸o˜es.
A utilizac¸a˜o de um elemento sentinela ao final do vetor, portanto, possibilita uma leve melhoria
no nu´mero de instruc¸o˜es executadas no pior caso. Esta diferenc¸a se torna mais pronunciada a` medida
que consideramos valores maiores de N. Para N=1, por exemplo, os dois algoritmos executam o mesmo
nu´mero de instruc¸o˜es. A partir de N=2, o algoritmo B apresenta melhor desempenho. No casos de
algoritmo com expresse˜s mais complexas para o nu´mero de instruc¸o˜es no pior caso, e´ frequente
vermos situac¸o˜es em que certo algoritmo passa a ser consistentemente melhor do que outro apenas
a partir de certos valores do tamanho da entrada de dados.
4 Exerc´ıcios
1. Escrever um trecho de co´digo que percorre um dado vetor de inteiros v e encontra o maior
elemento de v. (Na˜o e´ necessa´rio escrever co´digo pedindo ao usua´rio para entrar com os valores
de v. Assuma que v ja´ foi definido e preenchido antes de seu co´digo ser executado.)
2. Utilizando o algoritmo desenvolvido para a questa˜o anterior, determinar se o nu´mero operac¸o˜es
realizadas pelo seu algoritmo pode variar dependendo apenas dos valores armazenados em v.
Em outras palavras, imaginando que o tamanho de v e´ um valor n fixo, determinar se existe um
“melhor caso” dos dados armazenados em v, de forma que o nu´mero de operac¸o˜es realizadas
pelo algoritmo seja menor do que o caso mais geral. Se existir um melhor caso, descreveˆ-lo.
Se na˜o existir, justificar sua resposta.
3. Escrever um algoritmo que realize alguma tarefa sobre um vetor de inteiros de n posic¸o˜es e
que execute uma quantidade de instruc¸o˜es que e´ maior do que n2.
4. Escrever um algoritmo que chame o algoritmo A, conforme implementado neste material, e
realize um nu´mero total de instruc¸o˜es superior a n2.
5. Escrever um algoritmo para realizar a seguinte tarefa: encontrar o menor valor armazenado em
um vetor, cujos valores na˜o sa˜o conhecidos de antema˜o e podem estar fora de ordem. Descrever
o melhor e o pior casos deste algoritmo.
6. Considere dois algoritmos com as seguintes expresso˜es para o nu´mero de instruc¸o˜es realizadas
no pior caso: Algoritmo 1 = n2 − n + 1; Algoritmo 2: 3n + 7. O gra´fico abaixo ilustra estas
duas func¸o˜es. Encontre o tamanho da entrada a partir do qual o Algoritmo 2 passa a executar
um nu´mero de instruc¸o˜es no pior caso que e´ consistentemente inferior a`quele do Algoritmo 1.
4