Complexidade de Algoritmos

Elementos de an´alise de programas
David D´eharbe∗
DIMAp/UFRN
18 de setembro de 2003

Sum´ ario 1 Introdu¸ c˜ ao

1

2 O que ´ e an´ alise de algoritmos ?
2.1 Dicas para avaliar a complexidade de
2.1.1 Algoritmos iterativos . . . . .
2.1.2 Algoritmos recursivos . . . .
2.1.3 Considera¸c˜ oes . . . . . . . . .
2.2 Compara¸c˜ ao de algoritmos . . . . . .

um algoritmo.
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2
3
3
4
5
5

3 Defini¸ c˜ oes formais
3.1 Limite superior: a nota¸c˜ ao O . . . .
3.2 Limite inferior: a nota¸c˜ ao Ω . . . . .
3.3 Complexidade exata: a nota¸c˜ ao Θ .
3.4 Limite superior estrito: a nota¸c˜ ao o .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

6
6
7
7
7

4 Exemplo: O problema da soma da maior subseq¨ uˆ encia
4.1 Um algoritmo c´ ubico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2 Um algoritmo quadr´ atico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3 Um algoritmo linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
8
9
9

1

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.