Complexidade de Algotmo

Complexidade de
Algoritmos

Graduação
Ciência da Computação

Autor: Prof. Carlos Eduardo Gertners de Magalhães

Compiladores

SUMÁRIO
SUMÁRIO .......................................................................................................................... 2
LISTA DE FIGURAS......................................................................................................... 3
UNIDADE I – INTRODUÇÃO AO ESTUDO DA COMPLEXIDADE DE
ALGORITMOS .................................................................................................................. 5
1.1 A complexidade no desempenho de algoritmos ....................................................... 5
1.2 Metodologia de cálculo de complexidade................................................................. 7
1.3 A complexidade do problema e a intratabilidade ................................................... 11
UNIDADE II - CONCEITOS BÁSICOS DE COMPLEXIDADE .................................. 24
2.1 Medidas de complexidade....................................................................................... 24
2.2 Complexidades de tempo e de espaço .................................................................... 26
2.3 A complexidade de algoritmos e a comparação entre complexidades ................... 29
2.4 Ordens assintóticas.................................................................................................. 30
2.5 Análise do desempenho de algoritmos por tempo de execução – uso da notação O
(Ômicron)...................................................................................................................... 32
UNIDADE III - ANÁLISE DAS COMPLEXIDADES NO PIOR CASO – PESSIMISTA
– E NO CASO MÉDIO – MEDIANA.............................................................................. 49
3.1 Conceitos básicos.................................................................................................... 49
3.2 Equações de complexidade