Algoritmos Avançados

Prévia do material em texto

Algoritmos Avançados 
Prof. José Luiz Rosa – jose.anjos@estacio.br 
Ementa 
 
 
 Análise de Algoritmo 
 
 Recursividade 
 
 Algoritmos de Ordenação 
 
 Estruturas de dados dos tipos Árvore 
 
 Algoritmos em Grafos 
Bibliografia Básica 
 
ASCENCIO, Ana Fernanda Gomes; ARAÚJO, Graziela Santos de. 
Estruturas de Dados: algoritmos, análise da complexidade e 
implementações em JAVA, C/C++. São Paulo: Pearson Prentice Hall, 
2010. 
 
CORMEN, T. Desmistificando algoritmos. Rio de Janeiro: Elsevier, 
2014. 
 
Koffman, Elliot B.; Wolfgang, Paul A. T. Abstração, Estrutura de 
Dados e Projeto Usando C++. Rio de Janeiro: LTC, 2008. 
Bibliografia Complementar 
 
CELES, Waldemar; CERQUEIRA,Renato;RANGEL,José 
Lucas. Introdução a Estrutura de Dados com técnicas de 
programação em C. Rio de Janeiro : Elsevier, 2004. 
 
DROZDEK, Adam. Estrutura de dados e Algoritmos em C++. São 
Paulo: Pioneira Thomson Learning, 2005. 
 
EDELWEISS, N, GALANTE, R. M., Estrutura de Dados, Volume 18 - 
Série Livros Didáticos Informática UFRGS.1.ed.RS: Bookman, 2009. 
FORBELLONE, André Luiz Villar; EBERSPACHER, Henri 
Frederico. Lógica de Programação: A construção de Algoritmos e 
Estrutura de Dados. 3. ed. São Paulo: Makron Books, 2005. 
 
JEFF, E. Como pensar em algoritmo. Rio de Janeiro: LTC, 2010. 
 
KOFFMAN, Elliot B., WOLFGANG, Paul A.T., Objetos, Abstração, 
Estrutura de dados e Projeto usando C++, 1. ed. Rio de Janeiro: 
LTC,2008. 
 
SZWARCFITER, Jayme Luiz; MARKENZON, Lilian. Estruturas de 
dados e seus algoritmos. 3. ed. Rio de Janeiro, RJ: LTC, 2010. viii, 
302 p. ISBN 978-85-216-1750-1. 
Análise de Algoritmo 
 
- Revisão de C++ 
 
 . Array 
 . Registro (struct) 
 . Ponteiro 
 . Função. 
 
- Complexidade (notação O) 
Revisão de C++ 
 
Tipos 
 
 . int (inteiro): 10 
 . float (ponto flutuante de precisão simples): 10.0 
 . double (ponto flutuante de precisão dupla): 10.0 
 . char (caractere): 'A' 
 . bool (lógico): true/false 
 . void (especifica que uma função não retorna valor) 
Enumeração (contém um conjunto de valores especificados pelo 
usuário): 
 
enum binario {zero, um}; 
int valor; 
 
cout << "Numero: "; 
cin >> valor; 
if (valor == zero) 
 cout << "Zero" << endl; 
else 
 if (valor == um) 
 cout << "Um" << endl; 
 else 
 cout << "Valor fora de limite!" << endl; 
Outro exemplo: 
 
enum graus {c = 100, f = 212}; 
int temperatura; 
 
cout << "Temperatura em que a água pura ferve: "; 
cin >> temperatura; 
cout << "A água ferve a " << temperatura; 
if (temperatura == c) 
 cout << " graus Celsius." << endl; 
else 
 cout << " graus Fahrenheit." << endl; 
Typedef (declara um nome para um tipo): 
 
 
typedef float pontoFlutuantePrecisaoSimples; 
typedef double pontoFlutuantePrecisaoDupla; 
 
pontoFlutuantePrecisaoSimples f; 
pontoFlutuantePrecisaoDupla d; 
 
cout << "Tamanho do tipo float : " << sizeof (f) << endl; 
cout << "Tamanho do tipo double: " << sizeof (d) << endl; 
Constante (não permite a redefinição de um objeto após ser 
iniciado): 
 
const int limite = 100; 
 
A tentativa de redefinir “limite”, gera erro de compilação: 
 
limite = 50; 
[Error] assignment of read-only variable 'limite' 
 
Definir “limite” sem iniciá-la, gera erro de compilação: 
 
const int limite 
[Error] uninitialized const 'limit' 
Array 
 
Um array é um agregado de elementos de mesmo tipo. Declara-se 
um array em C++ como: 
 
tipo nome_array [quantidade_elementos] 
 
Por exemplo, a declaração: int v[3]; define um array de elementos 
“int”, de nome “v” e tamanho “3” (possui 3 elementos). 
Os elementos são indexados, sendo que o primeiro elemento 
está na posição 0 (zero), e o último, na posição “tam – 1”. 
 
int v[3]; 
 
v[0] = 1; 
v[1] = 10; 
v[2] = 100; 
Um array pode ter mais de uma dimensão (multidimensional): 
 
double localizacao [10][15]; 
 
Sendo válida a atribuição: 
 
localizacao [7][12] = 3.45 
 
Um array pode ser iniciado por uma lista de valores: 
 
char vogal [ ] = { 'a' , 'e' , 'i' , 'o' , 'u' } ; 
 
Fazer: cout << "Segunda vogal: " << vogal [1]; resulta em: 
Segunda vogal: e 
Estrutura (struct) 
 
Uma struct é um agregado de elementos que podem ser de tipos 
diferentes. 
 
struct letra 
{ 
 char simbolo; 
 int ascii; 
}; 
 
 
Observe o ponto-e-vírgula após a chave de fechamento. 
O acesso aos membros da struct se faz por meio do operador 
ponto ( . ): 
 
struct letra letra_A; 
 
letra_A.simbolo = 'A'; 
letra_A.ascii = 65; 
 
Pode-se definir um array de struct: 
 
struct letra vogais[5]; 
 
vogais[0].simbolo = 'A'; 
vogais[0].ascii = 65; 
Para evitar ter de escrever “struct letra”, pode-se utilizar typedef: 
 
typedef struct letra str_letra; 
 
struct letra 
{ 
 char simbolo; 
 int ascii; 
} ; 
 
str_letra letra_A; 
 
Ponteiro 
 
Uma variável do tipo ponteiro armazena um endereço de memória. 
Declara-se uma variável ponteiro, colocando-se um asterisco 
entre o tipo e o nome da variável: 
 
int *p; 
 
Uma forma de iniciar a variável “p”, é atribuir à mesma o endereço 
de outra variável por meio do operador de endereço &: 
 
int a; 
p = &a 
Não se pode atribuir um valor inteiro à variável “p”, pois a mesma 
não é do tipo “int”, e sim, um ponteiro para “int” (armazena o 
endereço inicial de memória onde está armazenado um valor do 
tipo int. Por exemplo, fazer: 
 
p = 10; 
 
gera a seguinte mensagem de erro na compilação: 
 
[Error] invalid conversion from 'int' to 'int*' 
 
A operação básica sobre um ponteiro é a derreferência (também 
chamada de indireção), pela qual faz-se referência ao objeto 
apontado pelo ponteiro. 
Esta operação utiliza o operador de derreferência *. Por exemplo: 
 
*p = 10; 
Fazer *p = 10; faz com que o endereço apontado por p (variável a) 
receba o valor 10 (lembre que “a” é uma variável inteira, e que 
“p” contém o endereço desta variável). 
 
int a , *p; 
p = &a 
 
*p = 10; 
 
cout << "*p = " << *p << endl; 
cout << "a = " << a << endl; 
 
Exibirá o valor 10, pois ambas as instruções exibem o conteúdo 
da mesma posição de memória. 
Porém, executar: 
 
cout << "p = " << p << endl; 
 
Produz como resultado: 
 
p = 0x6ffdec 
 
 
Observando que o endereço é mostrado em hexadecimal, e pode 
variar de sistema para sistema no qual o código seja executado. 
Ponteiros e arrays são intimamente relacionados. O nome de um 
array é um ponteiro para seu elemento inicial. Seja: 
 
int *p; 
int v[ ] = {1,2}; 
 
Fazer: 
 
p = v; 
 
é o mesmo que fazer: 
 
p = &v[0]; 
Aplicar um dos operadores aritméticos: + , - , ++ ou -- a ponteiros, 
faz com que o ponteiro aponte para uma posição de memória 
posterior ou anterior tantas posições quantas forem o tamnho do 
tipo definido para o ponteiro. Em uma plataforma na qual o valor 
do tipo int ocupe 4 bytes de memória, executar: 
 
int a; 
cout << "Tamanho do tipo int: " << sizeof (a) << endl; 
 
Faz com que seja exibido: 
 
Tamanho do tipo int: 4 
 
Então, as execuções abaixo produzem: 
 
int a, *p; 
p = &a ; 
 
cout << "p = " << p << endl; // exibe: p = 0x6ffdec 
p++; 
cout << "p = " << p << endl; // exibe: p = 0x6ffdf0 
p = p + 3; 
cout << "p = " << p << endl; // exibe: p = 0x6ffdfc 
p--; 
cout << "p = " << p << endl;// exibe: p = 0x6ffdf8 
Deve-se atentar para o fato de as variáveis “p” e “a” estarem 
alocadas em diferentes posições de memória: 
 
int a, *p; 
p = &a ; 
 
cout << "Endereço de p = " << &np << endl; // exibe: p = 0x6ffdf0 
cout << "Endereço de a = " << &na << endl; // exibe: p = 0x6ffdfc 
 
Referência 
 
Uma referência é um nome alternativo para uma um objeto. Ao 
fazer: 
 
int i; 
int &j = i; 
 
tem-se que “i” e “j” referenciam a mesma posição de memória. 
 
Dessa forma, fazer: i = 10; é o mesmo que fazer: j = 10; ; da 
mesma forma, fazer: cout << i; é o mesmo que fazer: cout << j; 
 
 
Adicionalmente, conforme mostra a saída do código abaixo: 
 
int x; 
int &y = x; 
 
cout << “Endereço de x: " << &x << endl; // exibe: 0x6ffdec 
cout << “Endereço de y: " << &y << endl; // exibe: 0x6ffdec 
 
Tem-se que “x” e “y” são a mesma variável de memória. 
Ponteiro para estrutura 
 
Utiliza-se o operador “new” para alocar memória. O endereço 
retornado por “new” pode ser atribuído a um ponteiro. 
 
struct Livro { 
 string nome; 
 string autor; 
 string editora; 
 int ano_publicacao; 
}; 
 
typedef struct Livro TLivro; 
TLivro *pLivro; 
pLivro = new TLivro; 
Para manipular os membros da struct, é utilizado o operador 
“derreferência a ponteiro para estrutura”, cujo símbolo é: ->. 
 
struct Livro { 
 string nome; 
 string autor; 
 string editora; 
 int ano_publicacao; 
}; 
typedef struct Livro TLivro; 
TLivro *pLivro; 
pLivro = new TLivro; 
 
pLivro->nome = "A Linguagem de Programação C++"; 
pLivro->autor = "Bjarne Stroustrup"; 
pLivro->editora = "Bookman"; 
pLivro->ano_publicacao = 2000; 
Um dos campos da estrutura, pode ser um ponteiro para a 
própria estrutura, permitindo uma iteração entre as diversas 
alocações, ou seja, cria uma lista encadeada. 
Por exemplo, seja a declaração abaixo: 
 
typedef struct Agenda TAgenda; 
 
struct Agenda { 
 string nome; 
 TAgenda *prox; 
}; 
 
TAgenda *a, *antes, *prim; 
Vamos alocar a estrutura na memória: 
 
a = new TAgenda; 
 
Agora, vamos armazenar o endereço da próxima estrutura. 
Porém, como não há, ainda, uma próxima estrutura alocada, o 
próximo endereço apontará para NULL: 
 
a->prox = NULL; 
 
O próximo passo é armazenar o nome: 
 
a->nome ="José"; 
 
Quando alocarmos memória para a próxima estrutura, o endereço 
da estrutura anterior se perderá. Então, deve-se guardar essa 
informação antes da próxima alocação. Para tal, será utilizada a 
variável “antes”: 
 
antes = a; 
 
Uma vez que “antes” e “a” são ponteiros para a struct “Tagenda”, 
tanto “antes” como “a” possuem, a partir de agora, o mesmo 
conteúdo, ou seja, o endereço de memória que aponta para a 
estrutura alocada atualmente. 
Como foi a primeira alocação, vamos armazenar o endereço da 
primeira alocação: 
 
prim = a; 
Graficamente, teríamos: 
nome: "José" 
 
*prox 
prim 
a 
antes 
Pronto! Podemos alocar o próximo endereço: 
 
a = new TAgenda; 
 
O que se tem após essa nova alocação é: 
 
 
 
 
 
 
 
 
 
Observe que não há ligação entre as estruturas. 
nome: "José" 
 
*prox 
prim antes 
a 
nome: 
 
*prox 
Para preencher o campo “nome” da nova alocação, será utilizado 
o ponteiro “a”, que possui o endereço desta alocação: 
 
a->nome = "Luiz"; 
 
 
 
 
nome: "José" 
 
*prox 
prim antes 
a 
nome: "Luiz" 
 
*prox 
 
O endereço da alocação atual ( “a” ) será armazenado no campo 
“prox” da alocação passada. Quem armazena o endereço da 
última alocação é o ponteiro “antes”. Faz-se, então: 
 
antes->prox = a; 
 
 
nome: "José" 
 
*prox 
prim 
a 
antes 
nome: "Luiz" 
 
*prox 
 
O endereço da próxima alocação ainda não existe. Então, o 
campo “prox” da alocação atual deve apontar para NULL: 
 
a->prox = NULL; 
 
 
nome: "José" 
 
*prox 
prim 
a 
antes 
nome: "Luiz" 
 
*prox 
Novamente, quando alocarmos memória para a próxima 
estrutura, o endereço da estrutura anterior se perderá. Então, 
deve-se guardar essa informação antes da próxima alocação. 
Para tal, será utilizada a variável “antes”: 
 
antes = a; 
 
 
nome: "José" 
 
*prox 
prim 
a 
antes 
nome: "Luiz" 
 
*prox 
Para exibir as informações armazenadas nas diversas estruturas 
alocadas em memória, é necessário retornar ao endereço da 
primeira alocação. Faz-se isso, atribuindo ao ponteiro “a” o 
conteúdo do ponteiro “prim”: 
 
a = prim; 
 
Antes de continuar, devemos nos certificar que houve, pelo 
menos, uma alocação, ou seja, devemos testar se o conteúdo de 
“a” é diferente de NULL. 
 
if (a != NULL) 
 
Se houve alocação, deve-se imprimir o campo “nome” enquanto 
o campo “prox” for diferente de NULL: 
 
do 
{ 
 cout << a->nome << " "; 
 a = a->prox; 
} 
while (a != NULL); 
 
Quando o campo “prox” for igual a NULL, a iteração é encerrada. 
Para finalizar, utiliza-se o operador “delete” na desalocação da 
memória alocada com “new” : 
 
delete a; 
O código completo fica como: 
 
#include <iostream> 
using namespace std; 
 
typedef struct Agenda TAgenda; 
struct Agenda { 
 string nome; 
 TAgenda *prox; 
}; 
 
int main(int argc, char** argv) { 
 TAgenda *a, *antes, *prim; 
 
 a = new TAgenda; 
 a->prox = NULL; 
 a->nome = "Jose"; 
 antes = a; 
 prim = a; 
 a = new TAgenda; 
 a->nome = "Luiz"; 
 antes->prox = a; 
 a->prox = NULL; 
 antes = a; 
 
 a = prim; 
 if (a != NULL) 
 do 
 { 
 cout << a->nome << " "; 
 a = a->prox; 
 } 
 while (a != NULL); 
 
 delete a; 
 
 return 0; 
 
} // fim da função main 
Função 
 
Uma função é uma estrutura de programa que possui o tipo de 
valor devolvido (tipo da função), um nome e, entre parênteses, 
nenhum ou muitos argumentos. Se especificados, os argumentos 
devem ser fornecidos na chamada da função. 
Então, a assinatura de uma função é como: 
 
tipo_valor_de_retorno nome_da_função (tipo1, tipo2, ..., tipon); 
 
Uma função do tipo “void” é uma função que não retorna valor. 
Na declaração da função, são apresentados somente os tipos dos 
argumentos, se existirem. Já na definição da função, os 
argumentos devem conter, além dos tipos, seus nomes 
respectivos. Uma função não declarada como “void”, deve 
retornar, ao final da definição, por meio do comando “return”, o 
valor produzido pela execução de seu código. 
Por exemplo, segue a declaração e a definição da função soma: 
 
int soma (int, int); // declaração 
 
int soma (int a, int b) // | início da definição 
{ // | 
 return a+b; // | 
} // | fim da definição 
A chamada de uma função é realizada dentro do corpo principal 
do programa (função “main”), ou dentro de outra função definida 
pelo programador: 
 
int main(int argc, char** argv) { 
 
 int x, y, s; 
 
 x = 1; 
 y = 2; 
 s = soma (x,y); 
 cout << "Soma: " << s << endl; 
 
 return 0; 
} 
Juntando todo o código: 
 
int soma (int, int); // declaração 
 
int main(int argc, char** argv) { 
 
 int x, y, s; 
 
 x = 1; 
 y = 2; 
 s = soma (x,y); 
 cout << "Soma: " << s << endl; 
 
 return 0; 
} 
 
int soma (int a, int b) // | início da definição 
{ // | 
 return a+b; // | 
} // | fim da definição 
Passagem de parâmetros que envolvem variáveis como “int” ou 
“double” é chamada de passagem por valor.Quando a passagem 
envolve ponteiro, diz-se tratar de passagem por referência. No 
exemplo anterior, ao término da execução da função soma, as 
variáveis “a” e “b” definidas como argumentos da função, tem 
seu ciclo de vida iniciando na chamada da função e terminando 
ao final da execução da função. Não há como acessar os valores 
de “a” ou de “b”. Já os valores das variáveis “x” e “y” continuam 
intactos. 
Já em uma passagem por referência, são os endereços que são 
passados para a função. Desta forma, ao término da execução da 
função, os valores das variáveis envolvidas na passagem de 
argumentos, passam a conter as alterações porventura ocorridas 
no corpo da função. 
 
 
Por exemplo, seja a declaração da função troca: 
 
void troca (int*, int*); 
 
E sua declaração: 
 
void troca (int* i, int* j) 
{ 
 int t; 
 
 t = *i; 
 *i = *j; 
 *j = t; 
} 
Vamos invocar (chamar) a função troca: 
 
 
int main(int argc, char** argv) { 
 
 int a = 5, b = 10; 
 
 cout << “a = “ << a << “ b = “ << b << endl; 
 troca (&a,&b); 
 cout << “a = “ << a << “ b = “ << b << endl; 
 
 return 0; 
} 
O código poderia ser reescrito, utilizando-se o operador de 
endereço & na definição da função: 
 
void troca (int &, int &); 
 
int main(int argc, char** argv) { 
 int a , b; 
 a = 5; 
 b = 10; 
 
 cout << "a = " << a << "b = " << b << endl; 
 troca (a,b); 
 cout << "a = " << a << "b = " << b << endl; 
 
 system ("pause"); 
 return 0; 
} 
void troca (int &i, int &j) 
{ 
 int t; 
 
 t = i; 
 i = j; 
 j = t; 
} 
Complexidade de Algoritmo 
 
Um algoritmo é uma sequência de ações executáveis cuja 
finalidade é resolver um dado problema por meio de abstrações 
do mundo real. 
Uma vez que sejam definidos os tipos que representarão os 
objetos do mundo real e que estejam dentro do contexto da 
resolução do problema, deve-se obter uma medida de quão 
otimizado é o algoritmo em termos de tempo de execução. 
Em havendo mais de uma forma de se processar os dados na 
resolução de um problema em particular, saber o quanto um 
algoritmo é melhor do que o outro, responde à pergunta sobre 
qual algoritmo apresenta melhor desempenho, ou seja, possui 
menor custo, para resolver o mesmo problema. 
Uma das formas que se pode utilizar, é a medida do tempo de 
execução de cada um dos algoritmos. 
Essa abordagem é falha, uma vez que é dependente da 
arquitetura de software (sistema operacional, compilador) e de 
hardware (processador, quantidade de memória, gpu etc.). 
 
Outra forma, seria medir o custo da resolução de um problema 
por um algoritmo, via modelo matemático, especificando-se as 
operações e seus custos de execução. 
Como todo modelo, deve-se fazer algumas simplificações, de 
forma a facilitar a obtenção de uma solução que, se não for a 
ideal, que pelo menos seja muito próxima dela. 
 
E essa aproximação se faz ignorando-se o custo de algumas 
operações comuns, levando-se em consideração, somente, as 
operações mais custosas. 
Para que se possa obter uma medida de custo de execução de 
algoritmos, permitindo a comparação entre eles, utiliza-se uma 
função denominada função de complexidade f. Pode-se dizer, 
então, que f(n) representa o tempo necessário que uma parte 
determinante do algoritmo leva para resolver um problema de 
tamanho n. Atente para o fato de que se trata de uma medida de 
esforço, de custo computacional, e não de tempo 
verdadeiramente. 
 
Como utilizaremos função, passemos à revisão de algumas 
funções que serão úteis no aprendizado desta disciplina. 
Função constante: f(n) = c 
 
É a função mais simples de todas, e, não importando qual seja o 
valor de n, f(n) sempre será igual à constante c. Por exemplo, o 
dobro de um valor sempre será obtido em um passo apenas (não 
importando que valor seja esse). 
 
Uma função cujo valor seja constante e igual a 1 é considerada 
fundamental. Sendo assim, dada uma função qualquer g(n) = 1 e 
f(n) = c, tem-se que: f(n) = cg(n). Esta função é útil na análise de 
algoritmos em virtude de caracterizar o número de passos 
necessários para executar uma operação básica, tal como uma 
operação de atribuição ou de comparação entre dois valores. 
Abaixo, tem-se a representação gráfica da função constante f(n) = 1: 
 
Função logaritmo: f(n) = log b n 
 
Para todo n maior do que zero, produz como resultado um valor x 
tal que: 
 
- n = 1 => x = 0. 
- n > 1 => log b n = x, se e somente se: b
x = n 
 
Então, log 2 8 = 3, pois, 2
3 = 8 
Sua representação gráfica é: 
 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
Função Logaritmo: f(n) = log(n) 
Função Linear: f(n) = n 
 
Para todo valor de n, f(n) é igual a n. Uma operação que compara 
um valor qualquer com os elementos de uma coleção, requer n 
operações de comparação. Se a coleção possuir 10 elementos, 
serão 10 comparações. Se forem 50 elementos, serão 50 
comparações. 
 
Sua representação gráfica é: 
 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
1 2 3 4 5 6 7 8 9 10 11 
Função Linear: f(n) = n 
Função n log n: f(n) = n log b n 
É uma função que cresce mais rápido que a função linear. 
Sua representação gráfica é: 
 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
1 2 3 4 5 6 7 8 9 10 11 
Função: f(n) = n log n 
Função quadrática: f(n) = n2 
É uma função que possui uma taxa muito alta de crescimento 
conforme o valor de n aumenta. 
Sua representação gráfica para poucos dados é: 
 
0 
20 
40 
60 
80 
100 
120 
1 2 3 4 5 6 7 8 9 10 
Função quadrática: f(n) = n2 
Porém, conforme a quantidade de dados se torna enorme, a 
representação gráfica toma a forma: 
 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
1 2 3 4 5 6 7 8 9 10 11 
Função quadrática: f(n) = n2 
Antes de prosseguir, uma revisão de matemática. 
Seja a progressão: 
a1 . a2 ... an-1 . an 
Cuja soma é: 
 s = a1 + a2 + ... + an-1 + an 
 Invertendo-se a ordem dos termos: 
 s = an + an-1 + ... + a2 + a1 
 Somando as duas expressões, vem: 
 2s = (a1+an) + (a2+an-1) + … + (an-1+a2) + (an+a1) 
 obtido pela soma de cada termo de uma expressão com o termo 
de mesma posição da outra expressão. 
Ou seja, 
 2s = (a1+an) + (a2+an-1) + … + (an-1+a2) + (an+a1) 
 
foi obtido como abaixo: 
 
(a1 + a2 + ... + an-1 + an) 
(an + an-1 + ... + a2 + a1) 
(a1 + an) + (a2 + an-1) + … + (an-1 + a2) + (an + a1) 
 
Se é uma progressão, tem-se que: 
 
(a1 + an) = (a2 + an-1) = ... = (an-1 + a1) 
 
tal como descoberto pelo matemático Carls Gauss, que obteve, 
rapidamente, a soma de todos os números inteiros entre 1 e 100. 
+ 
Então: 
2s = (a1 + an) + (a1 + an) + ... + (a1 + an) 
 
Como são n somas: 
 2s = n (a1 + an) 
 
O que resulta em: 
 
 
Ou seja: 
 
 s = 
 
n (a1 + an) 
 2 
 
i = 1 
i = n 
 ai = 
n ( a1 + n) 
 2 
 
Aplicando a teoria. 
 
Seja o trecho de algoritmo contendo dois laços aninhados: 
 
para i de 1 até n passo 1 
 para j de 1 até i passo 1 
 comando 
 
O número de operações executadas pelo laço mais interno é: 
1 + 2 + 3 + ... + (n-1) + n. 
Pela soma de Gauss, tem-se que: 
 
 
 
 
Ou seja, o número de operações é: 
 
 
Isto significa que a taxa de crescimento tem comportamento 
quadrático. 
i = 1 
i = n 
i = 1 + 2 + 3 + ... + (n - 1) +n = 
n ( 1 + n ) 
 2 
 
n + n2 
 2 
 
Função cúbica: f(n) = n3 
É uma função que possui uma taxa de crescimento ainda mais 
alta que a função quadrática. 
Sua representação gráfica é: 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
1 2 3 4 5 6 7 8 9 10 11 
Função cúbica: f(n) = n3 
Função Exponencial: f(n) = an 
 
Uma função exponencial possui uma taxa de crescimento bem 
mais alta que a cúbica. 
Muito comum em computação é a representação de um número 
por meio de um somatório de termos cuja base é 2 e o expoente 
varia de 0 a n. 
Por exemplo: 
 
15 = 20 + 21 + 22 + 23 
15 = 1 + 2 + 4 + 8 
 
 
Para um valor qualquer nesta base, temos: 
 
 
De forma geral: 
 
i = 0 
i = 3 
 2i 15 = 
i = 0 
i = n 
2i = 20 + 21 + 22 + ... + 2n 
i = 0 
i = n 
ai = a0 + a1 + a2 + ... + an = 
an+1 - 1 
a - 1 
 
Sua representação gráfica é: 
 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
1 2 3 4 5 6 7 8 9 10 11 
Função Exponencial: f(n) = an 
Juntando as representações gráficas de todas as funções, 
podemos comparar suas taxas de crescimento: 
 
 
 
 
 
 
 
 
 
 
 
Do gráfico obtemos: 
constante < logaritmo < linear < n log n < quadrática < cúbica < exponencial 
0 
10 
20 
30 
40 
50 
60 
70 
80 
90 
100 
1 2 3 4 5 6 7 8 9 10 11 
Comparativo entre todas as funções 
f(n) = c f(n) = log n f(n) = n f(n) = n log n 
f(n) = n^2 f(n) = n^3 f(n) = e^n 
Polinômio 
 
Vimos que um valor pode ser representado em termos de uma 
função polinomial, cuja base é 2, com o expoente variando de 
0 a n. Ou seja: 
f(n) = a0 + a1 + a2 + ... + an 
 
 Vimos que o número 15 é formado pela sequência: 
 
 15 = 20 + 21 + 22 + 23 
 
 Antes dele vem o 7: 20 + 21 + 22 
 
E, depois, vem o 31: 20 + 21 + 22 + 23 + 24 
Mas, como representar o valor 10? Simples, basta desconsiderar 
os termos: 20 e 22, considerando, apenas, os termos 21 e 23. Ou 
seja: 
 
10 = 0 x 20 + 1 x 21 + 0 x 22 + 1 x 23 
10 = 0 + 2 + 0 + 8 = 2 + 8 
 
No exemplo dado, pode-se dizer que: 
 
f(2) = 0 x 20 + 1 x 21 + 0 x 22 + 1 x 23 
 
é uma função polinomial, e que as constantes 0 e 1 que 
multiplicam os termos de base 2, são denominados coeficientes 
desse polinômio. 
Isto significa dizer que uma função polinomial tem a seguinte 
forma: 
f(n) = a0 + a1 n + a2 n
2 + ... + ad n
d 
 sendo que: 
 
 - Os valores a0, a1, a2, ... , ad são chamados de coeficientes do 
polinômio. 
 
- ad é diferente de zero. 
 
- O valor d é chamado grau do polinômio. 
Análise Assintótica 
 
 A análise de um algoritmo visa caracterizar seu tempo de 
execução por meio de uma função f(n) que leva em consideração 
o tamanho da entrada, mas que independe do software e do 
hardware. 
Por meio desta análise, algoritmos podem ser, relativamente, 
comparados, em termos de suas eficiências na resolução de um 
dado problema. 
 
Então, para se obter o tempo estimado de execução de um 
algoritmo, basta que se obtenha o número de Operações 
Primitivas executadas, tais como: 
- Operações de Atribuição 
- Operações Aritméticas 
- Operações Relacionais 
- Operações Lógicas 
- Invocação de uma função 
- Retorno de uma função 
- Desvio condicional 
- Acesso ao membro de uma estrutura 
- Acesso a uma posição de um array 
- Manipulação de conteúdo via ponteiro 
Essas operações correspondem a instruções de baixo nível com 
um tempo de execução constante. Contando-as, tem-se uma 
estimativa do tempo de execução do algoritmo em análise. 
Trata-se de estimativa, pois um algoritmo pode executar mais ou 
menos rapidamente em função do tamanho da entrada. 
Dentro deste conceito, algoritmos que executem, em função de n, 
uma quantidade de operações igual a: 
 
Algoritmo a: f(n) = n2 
Algoritmo b: f(n) = n2 + n 
Algoritmo c: f(n) = 10 n2 
 
são equivalentes, ou seja, pertencem à mesma ordem (n2), e seus 
tempos crescem, praticamente, à mesma velocidade, pois todos 
têm comportamento quadrático, isto é, o crescimento do número 
de operações cresce quadraticamente conforme aumenta o 
tamanho da entrada. 
Exemplificando, seja um programa contendo o trecho abaixo: 
 
 
time_t inicio, fim; 
 
time(&inicio); 
for (int i=0; i<n;i++) 
 for (int j=0; j<1E+3; j++); 
time(&fim); 
cout << "Tempo: " << difftime(fim,inicio); 
 
Executando-o por meio de um programa na linguagem C++, em 
um computador com CPU Intel® Core™ i7, 2.2GHz com 8GB de 
memória RAM, obtém-se os seguintes tempos de execução: 
 
n = 1E+3 : tempo = 0s 
n = 1E+6 : tempo = 2s 
n = 1E+7 : tempo = 23s 
n = 1E+8 : tempo = 231s 
n = 1E+9 : tempo = 2.328s 
A representação gráfica dos tempos de processamento é como 
segue: 
 
0 
500 
1000 
1500 
2000 
2500 
1 2 3 4 5 
Evolução do tempo de execução do algoritmo 
Apesar dos poucos dados observados de tempo de execução, 
nota-se, pela taxa de crescimento apresentado, tratar-se de uma 
função quadrática, ou seja, f(n) = n2: 
 
 
 
 
 
 
Isto significa que, qualquer algoritmo que tenha característica de 
uma função quadrática, terá seus tempos de execução variando 
conforme o gráfico apresentado acima. 
Já dois algoritmos cuja quantidade de operações seja: 
 
Algoritmo A: f(n) = n2 
Algoritmo B: f(n) = n + 1.000 
 
Não pertencem à mesma ordem, pois o primeiro tem 
comportamento quadrático, e o segundo, comportamento linear. 
 
Se n = 2, a quantidade de operações executadas por cada algoritmo 
é: 
 
Algoritmo A: 102 = 100 operações 
Algoritmo B: 10 + 1.000 = 1.010 operações 
 
Ou seja, o algoritmo A é 10 vezes mais rápido do que o algoritmo B. 
 
Entretanto, se n = 1.000, a quantidade de operações executadas é: 
 
Algoritmo A: 1.0002 = 1.000.000 
Algoritmo B: 1.000 + 1.000 = 2.000 
 
Ou seja, o algoritmo A é 500 vezes mais lento do que o algoritmo B. 
 
Seria interessante analisar o algoritmo levando-se em 
consideração uma entrada cujo tamanho fosse a média de todas 
as possíveis entradas. Porém, obter esta quantidade requer 
cálculos probabilísticos complexos, o que inviabiliza essa 
abordagem. 
 
Então, leva-se em consideração, na análise do algoritmo, um 
tamanho de entrada n correspondente ao pior caso, partindo do 
princípio que, analisando o pior caso, o algoritmo tenha tempos 
de execução menor para as demais entradas. 
A análise do pior caso baseia-se em valores enormes de n (n->∞), 
cujo comportamento da função é chamado assintótico. Neste 
cenário, os termos inferiores e as constantes multiplicativas 
podem ser descartados, uma vez que pouco ou nada contribuem 
na comparação entre as taxas de crescimento do tempo de 
resolução do problema. 
Na análise de algoritmos, nos interessa estudar funções 
assintoticamente não negativas, o que significa dizer que existe 
um valor no tal que f(n) > 0 para todo n > no. 
 
Contando operações primitivas de um algoritmo 
 
Como foi dito anteriormente, o tempo de execução de um 
algoritmo é diretamente relacionado à quantidade de operações 
primitivas executadas por ele. Então, deve-se obter essa 
quantidade visando-se comparar dois algoritmos. 
Também deve ser observado que, um algoritmo não 
necessariamente é sempre pior (ou melhor) do que o outro, o que 
dependerá da quantidade de dado a ser processado. Um 
algoritmo pode ter desempenho melhordo que outro para 1000 
dados, porém, ter desempenho pior do que o outro para bases 
com mais de 1000 elementos. 
Seja o algoritmo abaixo, que retorna o maior valor lido de um 
array de n posições: 
 
#include <iostream> 
using namespace std; 
 
int maiorElemento (int [], int n); 
int main(int argc, char** argv) { 
 
int a[5]; 
 a[0]=10; 
a[1]=35; 
a[2]=2; 
a[3]=5; 
a[4]=11; 
cout << "Maior:" << maiorElemento(a,5); 
return 0; 
} 
 
int maiorElemento (int arr[], int n) 
{ 
 int maiorElemento = arr[0]; 
 for (int i=1; i<n; i++) 
 if (arr[i] > maiorElemento) 
 maiorElemento = arr[i]; 
 return maiorElemento; 
} 
Vamos analisar o trecho que contém a função: 
 
int maiorElemento (int arr[], int n) 
{ 
 int maiorElemento = arr[0]; 
 for (int i=1; i<n; i++) 
 if (arr[i] > maiorElemento) 
 maiorElemento = arr[i]; 
 return maiorElemento; 
} 
Assumindo que as 
instruções primitivas 
possuem o mesmo 
custo de processamento, 
tem-se: 
Instrução Número de execuções 
int maiorElemento = arr [ 0 ] ; 1 
for (int i = 1; i < n; i++) 2n 
--------------------- 
1ª execução: 
 int i = 1 : 1 
 i < n : 1 
Demais execuções: 
 i++ : n - 1 
 i<n : n - 1 
Resultado: 
 1+1+n-1 +n-1 = 2n 
 if ( arr [ i ] > maiorElemento ) n-1 
--------------------- 
1 instrução “n-1” vezes 
 maiorElemento = arr [ i ] ; n-1 
--------------------- 
1 instrução. 
Como a condição é sempre true, a 
instrução será executada “n-1” 
vezes 
return maiorElemento; 1 
int maiorElemento (int [] arr, int n) 
{ 
} 
Observação1: 
 
O “for” inicia “i” com “1” (i=1) e testa a condição (i<n) somente 1 
vez, ou seja, essas duas instruções são executadas 
sequencialmente. Depois, o “for” repete as instruções “i++” e 
“i<n” por “n-1” vezes. 
 
Por exemplo, se n for igual a 5: 
Sequencial : i=1 ; i<5 (i é 1 ; i < 5 => true) 
Repetição 1 : i++ ; i<5 (i é 2 ; i < 5 => true) 
Repetição 2 : i++ ; i<5 (i é 3 ; i < 5 => true) 
Repetição 3 : i++ ; i<5 (i é 4 ; i < 5 => true) 
Repetição 4 : i++ ; i<5 (i é 5 ; i < 5 => false) 
Calculando o custo 
 
No pior caso, tem-se que o maior elemento encontra-se na última 
posição e o array está ordenado: 
 
f(n) = 1 + 2n + n-1 + n-1 + 1 
f(n) = 4n 
Instrução Número de execuções 
int maiorElemento = arr [ 0 ] ; 1 
for (int i = 1; i < n; i++) 2n 
--------------------- 
1ª execução: 
 int i = 1 : 1 
 i < n : 1 
Demais execuções: 
 i++ : n - 1 
 i<n : n - 1 
Resultado: 
 1+1+n-1 +n-1 = 2n 
 if ( arr [ i ] > maiorElemento ) n-1 
--------------------- 
1 instrução “n-1” vezes 
 maiorElemento = arr [ i ] ; 0 
--------------------- 
1 instrução. 
Como a condição é sempre false, a 
instrução nunca será executada. 
return maiorElemento; 1 
Porém, se o elemento 
estiver na primeira 
posição do array, 
a instrução após o “if” 
nunca será executada. 
O custo de execução: 
 
f(n) = 1 + 2n + n-1 + 0 + 1 
f(n) = 4n + 1 
 
É obtido como mostrado 
ao lado. 
Se o “for” iniciar a 
variável “i” com 0, 
o custo de execução 
para o pior caso 
resulta em: 
 
f(n) = 1 + 2n + 2 + n + n + 1 
f(n) = 4n + 4 
 
 
 
Instrução Número de execuções 
int maiorElemento = arr [ 0 ]; 1 
for (int i = 0; i < n; i++) 2n+2 
--------------------- 
1ª execução: 
 int i = 1 : 1 
 i < n : 1 
Demais execuções: 
 i++ : n 
 i<n : n 
Resultado: 
 1+1+n +n = 2n + 2 
 if (arr [ i ] > maiorElemento) n 
 maiorElemento = arr [ i ] ; n 
return maiorElemento; 1 
Definindo-se o tamanho do array (n), obtemos a quantidade de 
operações executadas: 
 
 
 
 
Tanto “4n” como “4n+4” são funções de complexidade de tempo 
do algoritmo. Conforme a quantidade de elementos cresce (tende 
ao infinito), a adição de 4 operações no termo “4n+4” deixa de ser 
relevante. Sendo assim, conforme o tamanho de entrada (n) 
cresce muito, pode-se descartar certos termos na função de 
custo, mantendo-se, apenas, os termos importantes para a 
obtenção desse custo. 
 4n 4n+4 
2 8 12 
100 400 404 
1E10 4E10 4E10 
Vamos fazer outro exemplo. Suponha que se deseja conhecer o 
maior valor de cada linha de um array numérico. Suponha, 
também, tratar-se de uma matriz quadrada (a qual possui o 
número de linhas igual ao número de colunas). 
O programa completo é como mostrado abaixo: 
#include <iostream> 
using namespace std; 
int * maiorElementoPorLinha (int [][3], int n); 
 int main(int argc, char** argv) { 
 int a[3][3], * me; 
 
 a[0][0]=10; 
 a[0][1]=35; 
 a[0][2]=46; 
 a[1][0]=11; 
 a[1][1]=19; 
 a[1][2]=121; 
 a[2][0]=97; 
 a[2][1]=86; 
 a[2][2]=12; 
 me = maiorElementoPorLinha(a,3); 
 for (int i=0; i<3; i++) 
 cout << me[i] << endl; 
 return 0; 
 } 
 
 
 int *maiorElementoPorLinha (int arr[][3], int n) 
 { 
 int *maiorElemento; 
 maiorElemento = new int[n]; 
 
 for (int i=0; i<n; i++) { 
 maiorElemento[i] = arr[i][0]; 
 for (int j=0; j<n; j++) 
 if (arr[i][j] > maiorElemento[i]) 
 maiorElemento[i] = arr[i][j]; 
 } 
 return maiorElemento; 
} 
 
Analisando a função “maiorElementoPorLinha”. 
Novamente, vamos assumir que as instruções primitivas 
possuem o mesmo custo de processamento. 
 
 
 
 
 
 
 
 
 
 
 
Instrução Número de execuções 
maiorElemento = new int [ n ] ; 1 
for (int i = 0; i < n; i++) { 2n+2 
 maiorElemento [ i ] = arr [ i ] [ 0 ] ; n 
 for (int j = 0; j < n; j++) n(2n+2) 
 if ( arr [ i ] [ j ] > maiorElemento [ i ] ) n2 
 maiorElemento [ i ] = arr [ i ] [ j ] ; n2 
} 
return maiorElemento; 1 
int *maiorElementoPorLinha (int arr[][3], int n) 
{ 
 
} 
No pior caso (no qual a condição do “if” é sempre true): 
f(n)=1+2n+2+n+2n2+2n+n2+n2+1=4n2+5n+4 
 
No melhor caso (no qual a condição do “if” é sempre false): 
f(n)=1+2n+2+n+2n2+2n+n2+1=3n2+5n+4 
Vamos, agora, somar todos os elementos que estão abaixo da 
diagonal principal de uma matriz, para exemplificar os casos em 
que o “for” interno tem por limite o valor da variável de controle 
do “for” “externo”. 
Os elementos da Diagonal Principal (DP) estão em células cujas 
coordenadas são iguais, ou seja, o “i” é igual ao “j”, como 
destacado abaixo: 
 
(0,0) (0,1) (0,2) (0,3) 
(1,0) (1,1) (1,2) (1,3) 
(2,0) (2,1) (2,2) (2,3) 
(3,0) (3,1) (3,2) (3,3) 
Assim sendo, para somar todos os elementos abaixo da diagonal 
principal de uma matriz, devemos somar todos os elementos 
“mat (i,j)” cujo valor de “j” seja menor do que o valor de “i”: 
 
(0,0) (0,1) (0,2) (0,3) 
(1,0) (1,1) (1,2) (1,3) 
(2,0) (2,1) (2,2) (2,3) 
(3,0) (3,1) (3,2) (3,3) 
Seja a matriz 4 x 4: 
 
 
 
 
 
 
 
 
A soma dos elementos abaixo da DP é 66 (5 + 9 + 10 + 13 + 14 + 15). 
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 
Vamos criar um programa para obter essa soma, cujo código é 
como segue: 
 
#include <iostream> 
using namespace std; 
const int n = 4; 
int somaElementosAbaixoDaDP (int [ ] [ n ] ) ; 
int main(int argc, char** argv) { 
 int mat [ n ] [ n ] ; 
 mat[0][0] = 1; mat[0][1] = 2; mat[0][2] = 3; mat[0][3] = 4; 
 mat[1][0] = 5; mat[1][1] = 6; mat[1][2] = 7; mat[1][3] = 8; 
 mat[2][0] = 9; mat[2][1] = 10; mat[2][2] = 11; mat[2][3] = 12; 
 mat[3][0] = 13; mat[3][1] = 14; mat[3][2] = 15; mat[3][3] = 16; 
 cout <<"S= " << somaElementosAbaixoDaDP (mat) << endl; 
 
 return 0; 
} 
int somaElementosAbaixoDaDP (int mat [ ] [ n ] ) 
{ 
 int s = 0 ; 
 for (int i = 0 ; i < n ; i++) 
 for (int j = 0 ; j < i ; j++) 
 s += mat [ i ] [ j ] ; 
 return s; 
} 
Vamos analisar somaElementosAbaixoDaDP, função que realiza 
tal procedimento. Assuma que as instruções primitivas possuem 
o mesmo custo de processamento. 
Como o “for j” tem seu limite superior alterado a cada passo do 
“for i”, ele executará um número variável de vezes e, em 
consequência, a linha de comando executada por “for j” também 
terá um número variável de execuções. 
Vamos fazer o “computador chinês” para descobrir a quantidade 
de vezes que o laço “for (j=0; j<i; j++)” e a linha de comando 
“s += mat[i][j];” são executados. 
 
 
 
 
 
 
 
No “for j” tem-se uma PA de razão 1: 
PA: 1 . 2 . 3 ... n 
i j for (j=0; j<i; j++) s += mat[i][j]; 
0 0..0 1 0 
1 0..1 2 1 
2 0..2 3 2 
... ... ... ... 
n-1 0..n-1 n n-1 
A soma desta PA dá: n(1+n)/2 execuções de laço. Porém, esta 
soma deve ser multiplicada por dois, pois o “for” possui duas 
operações (“i++” e “i<n”). Então, o número total de operações 
executadas pelo for é: 2n(1+n)/2 = n(1+n) = n + n2. 
A soma ”s += mat[i][j];” trata-se, igualmente, de uma PA, cujo 
somatório é: n(0 + n-1)/2 = (n2 - n)/2. 
 
Instrução Número de execuções 
int s = 0; 1 
for (int i = 0 ; i < n ; i++) 2n+2 
 for (int j = 0 ; j < n ; j++) n + n2 
 s += mat [ I ] [ j ] ; (n2 - n)/2 
return s; 1 
int somaElementosAbaixoDaDP (int arr[][n]) 
{ 
} 
Aqui, o melhor caso é igual ao pior caso, e o custo de execução 
do algoritmo é: 
f(n) = 1 + 2n + 2 + n + n2 + (n2 - n) + 1 
 
 
f(n) = 2 + 4n + 4 + 2n + 2n2 + n2 - n + 2 
 
 
f(n) = 3n2 + 5n + 8 
2 
2 
2 
Notação O 
 
A análise da complexidade de um algoritmo permite projetar 
algoritmos mais eficientes, ou, tendo duas soluções para o 
mesmo problema, pode-se calcular o custo de cada uma delas e 
escolher a de menor custo computacional. 
Por exemplo, sejam dois algoritmos para somar os elementos de 
um array. A primeira solução, utilizando um array bidimensional. 
A segunda solução, utilizando um array unidimensional. 
Solução 1: array bidimensional 
 
s = 0; // custo = 1 
for (int i=0; i<n; i++) // custo = 2+2n 
 for (int j=0; j<n; j++) // custo = n(2+2n) 
 s += mat[i][j]; // custo = n 
 
Custo: 1 + 2 + 2n + 2n + 2n2 + n = 2n2 + 5n + 3 
 
Solução 2: array unidimensional 
 
s = 0; // custo = 1 
for (int i=0; i<n; i++) // custo = 2+2n 
 for (int j=0; j<n; j++) // custo = n(2+2n) 
 s += mat[n*i + j]; // custo = 3n 
 
// operação 1: multiplicação (n*i) 
// operação 2: soma com j 
// operação 3: soma e atribuição a “s” 
// as três operações são executadas “n” vezes 
 
Custo: 1 + 2 + 2n + 2n + 2n2 + 3n = 2n2 + 7n + 3 
A primeira solução tem um custo menor do que a segunda 
solução. 
Em ambas, o melhor caso é igual ao pior caso. 
A análise da complexidade de um algoritmo, então, nos permite 
projetar algoritmos mais eficientes. Porém, devemos sempre 
levar em consideração, o tamanho “n” dos dados de entrada, 
pois nem sempre um algoritmo A que resolva o mesmo problema 
que um algoritmo B, executará menos operações do que o 
segundo. 
Por exemplo, sejam as funções: 
Algoritmo A: f(n) = n + 10000 
Algoritmo B: g(n) = 2n2 + 3n 
 
 n = 10 n = 100 n = 1000 
Algoritmo A 10010 10100 11000 
Algoritmo B 230 20300 2003000 
Dessa forma, para grandes quantidades de dados deve-se 
preferir o algoritmo A, pois ele tem desempenho melhor que B. 
A partir das funções estudadas anteriormente, obtém-se os 
vários tempos de execução para uma determinada configuração 
de máquina. Se, por hipótese, uma operação primitiva levar 1 ms 
para sua execução, tem-se os vários tempos de execução (em 
segundos), em função da taxa de crescimento da função: 
 
n f(n) = n f(n) = log(n) f(n)=nlog(n) f(n) = n2 f(n)=n3 f(n) = 2n 
10 0,01 0,003 0,033 0,1 1 1,024 
100 0,1 0,007 0,664 10 16,667 1,27E+27 
1000 1 0,01 9,966 1,00E+03 1,00E+06 1,10E+298 
Observe que para uma população de 1000 indivíduos, um 
algoritmo O(2n) leva 1,10E+298 segundos, ou 10288 séculos, para 
processar os dados, ao passo que um algoritmo O(nlog(n)) leva 
aproximadamente 10s para obter a solução do mesmo problema 
e um algoritmo O(n2) leva 17 minutos (aproximadamente). 
Conforme n tende ao infinito (n->∞) tem-se que o comportamento 
da função é chamado de assintótico, e os termos inferiores do 
polinômio que representam a função, bem como as constantes 
multiplicativas tornam-se irrelevantes, por contribuírem muito 
pouco na comparação entre os algoritmos e podem ser 
descartados. 
Tomando-se como exemplo os algoritmos anteriores, o 
importante é observar que f(n) tem crescimento linear, ao passo 
que g(n) tem crescimento quadrático. 
Dizemos que o algoritmo A é da ordem O(n) e o algoritmo B é da 
ordem O(n2). 
Pelo exposto, não faria sentido dizer que A é O(n + 10000) ou que 
B é O(2n2 + 3n). 
 
Isto posto, se f(n) é um polinômio de grau “d”, isto é: 
f(n) = ao + a1n + a2n
2 + ... + adn
d 
então, f(n) é O(d). 
 
Outros exemplos: 
O(n) : 4 n + 1000 
O(n2) : 3 n2 + n log n + 3 
O(2n) : 2n+3 + 3 n 
 
Uma função constante tem somente o primeiro termo do 
polinômio (n0). Diz-se, neste caso, que uma função constante tem 
ordem O(1), pois todo número elevado a zero é igual a 1. 
Assim sendo, dada uma função g(n) que mapeia inteiros não 
negativos em números reais, denotamos por O(g(n)) o conjunto 
de funções f(n), onde: 
0 ≤ f(n) ≤ cg(n) 
sendo “c” uma constante real maior que zero (c > 0) e “no“ uma 
constante inteira maior ou igual a um (no ≥ 1), para todo inteiro 
n ≥ no. 
Desta forma, dizemos que f(n) é O de g(n). 
E a representação gráfica é como: 
cg(n) 
f(n) 
no Tamanho da base (n) 
tempo de 
execução 
Tem-se, neste caso, que f(n) cresce a 
uma taxa proporcional à g(n). Podemos 
dizer que f(n) é de complexidade g(n), ou, 
simplesmente, que f(n) é O de g(n). 
A função g expressa um limite superior 
para valores assintóticos de f. Assim 
sendo, O(g(n)) tem como valor uma 
quantidade muito grande, não 
explicitamente definida, que não excede 
“c * g(n)”, para um “n” muito grande 
(n>no), sendo no o ponto a partir do qual 
f(n) é menor que g(n). 
 
cg(n) 
f(n) 
no n 
t 
Regras para Cálculo de Complexidade 
 
 
f(n) = O(f(n)) 
c * O(f(n)) = O(f(n)) * c 
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)) 
Assim sendo, a complexidade de um algoritmo será dada pela 
maior das complexidades encontradas. Por exemplo, o trecho 
abaixo tem complexidade O(n2): 
 
cin >> a; 
cin >> b; 
s = 0; 
if (a > b) 
 for(i = 0; i < n; i++) // O(n) 
 s += i; 
else 
 for(i = 0; i < n; i++) // O(n2) 
 for(j = 0; j < n; j++) 
 s += i*j; 
O(max(O(n),O(n2))) = O(n2) 
Outro exemplo: Multiplicação de matrizes 
 
Sejam duas matrizes “A” e “B”, ambas 3x3: 
a(0,0) a(0,1) a(0,2) 
a(1,0) a(1,1) a(1,2) 
a(2,0) a(2,1) a(2,2) 
A = 
b(0,0) b(0,1) b(0,2) 
b(1,0) b(1,1) b(1,2) 
b(2,0) b(2,1) b(2,2) 
B = 
a(0,0) a(0,1) a(0,2) 
a(1,0) a(1,1) a(1,2) 
a(2,0) a(2,1) a(2,2) b(0,0) b(0,1) b(0,2) 
b(1,0) b(1,1) b(1,2) 
b(2,0) b(2,1) b(2,2) 
Obtém-se a multiplicaçãodas matrizes pela soma das 
multiplicações dos elementos de cada da linha de “A” pelos 
elementos de cada coluna de “B”: 
A solução tem complexidade O(n3): 
 
for(i = 0; i < n; i++) // O(n2) 
 for(j = 0; j < n; j++) 
 c[i][j] = 0; 
for(i = 0; i < n; i++) // O(n3) 
 for(j = 0; j < n; j++) 
 for(k = 0; k < n; k++) 
 c[i][j] += a[i][k] * b[k][j]; 
 
 
 
 
O(max(O(n2),O(n3))) = O(n3)