Complexidade de algoritmo

Elementos de an´lise de programas a David D´harbe∗ e DIMAp/UFRN
18 de setembro de 2003

Sum´rio a 1 Introdu¸˜o ca 1

2 O que ´ an´lise de algoritmos ? e a
2.1 Dicas para avaliar a complexidade de
2.1.1 Algoritmos iterativos . . . . .
2.1.2 Algoritmos recursivos . . . .
2.1.3 Considera¸˜es . . . . . . . . . co 2.2 Compara¸˜o de algoritmos . . . . . . ca um algoritmo.
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

2
3
3
4
5
5

3 Defini¸˜es formais co 3.1 Limite superior: a nota¸˜o O . . . . ca 3.2 Limite inferior: a nota¸˜o Ω . . . . . ca 3.3 Complexidade exata: a nota¸˜o Θ . ca 3.4 Limite superior estrito: a nota¸˜o o . ca .
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

6
6
7
7
7

4 Exemplo: O problema da soma da maior subseq¨ˆncia ue 4.1 Um algoritmo c´bico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u 4.2 Um algoritmo quadr´tico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . a 4.3 Um algoritmo linear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8
8
9
9

1

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.