Complexidade de Algoritmos
DAS 5102 – Fundamentos da Estrutura da Informação
Prof. Dr. rer. nat. Daniel D. Abdala
[email protected]
Objetivos
Introduzir o conceito de análise de
algoritmos;
 Introduzir o conceito de complexidade
assintótica;
 Explicar via exemplos como medir a
complexidade de algoritmos;
 Explicar o conceito de complexidade
média de melhor e de pior caso.

Plano de Aula
Algoritmos
 Análise de Algoritmos
 Conceitos Básicos
 Complexidade no Tempo e no Espaço
 Notação Assintótica

Conceitos Básicos – Algoritmos
Algoritmo – Ferramenta para resolução
de problemas.
 Problemas são descritos via:

◦ Uma descrição de todos os seus parâmetros
de entrada (INPUT)
◦ Um enunciado sobre que propriedades a
solução deve satisfazer
Conceitos Básicos – Algoritmos
Exemplo
Entrada
Saída

: Problema de Ordenação
: Seqüência L (a1, ..., aN)
: L’ (a1’, ..., aN’) que é uma permutação
da entrada tal que a1’≤ a2’ ≤ ... ≤ aN’
Um Algoritmo é dito CORRETO se para todas
as possíveis entradas ele termina com a resposta correta.
Algoritmos Eficiente - Motivação

Dois computadores
◦ PC (106 instr/s)
◦ SC (108 instr/s)

Dois algoritmos de ordenação
◦ Alg1 – TAlg1 = 2N2
◦ Alg2 – TAlg2 = 50NlogN



Problema : Ordenar 106 números
 (10 ) instr
 20 10 s  5.56horas
SC – 210
instr / s
6 2
3
8
PC –
50  (106 ) log(106 )instr
 103 s  16.57 min
6
10 instr / s
Análise de Algoritmos

Análise de algoritmos é uma disciplina da computação que se preocupa em medir e analisar os recursos necessários por algoritmos para levar a termo
sua execução.
Complexidade no Tempo e no
Espaço (N)



Espacial – mede a quantidade de memória
que o algoritmo requer para sua execução
Temporal – mede o tempo, dada uma
entrada de dados, que o algoritmo requer
para produzir uma resposta (mais usado)
As medidas de análise utilizadas devem
conter as seguintes características:
◦ Ser independentes da tecnologia empregada
(hardware e software);
◦ Modelo matemático simplificado que representa
os fatores mais relevantes;
Complexidade no Tempo e no
Espaço (N)
Temporal – função que relaciona o tamanho
da entrada com o tempo de execução:
t = f(N)
 Espacial – função que relaciona o tamanho da
entrada com o espaço de armazenamento
requerido:
e = g(N)

Exemplo: Ordenação de Inteiros
Exemplo: Ordenação de Inteiros
Exemplo: Ordenação de Inteiros
Exemplo: Ordenação de Inteiros
Considerações

Sempre que criamos um algoritmo, existem três
perguntas que devem ser formuladas:
1. O algoritmo é correto?
2. Quanto tempo ele leva em função da entrada N?
3. O problema pode ser resolvido de uma maneira melhor?
Notação Assintótica

Também conhecida com notação O
◦ (diz-se big O)

Definição:
Considere uma função f(n) não negativa para todos
n>=0. Diz-se que f(n) é O(g(n)) e escrevemos f(n)
= O(g(n)), se existem um inteiro n0 e uma constante c>0, tais que para todo inteiro m>=n0, f(n) <
c g(n).

Em resumo: Podemos ignorar as constantes!
Classes de Complexidade
Designação
Constante
Logarítmica
Logarítmica quadrática
Linear
N log N
Quadrática
Cúbica
Exponencial
Função
c
log N
log2N
N
N log N
N2
N3
2N
Exemplo: Tempo de execução
Considere a seguinte situação. O problema
apresentado a seguir foi resolvido de cinco
maneiras diferentes, resultando em cinco
algoritmos (A1 ... A5).
 Tais algoritmos foram implementados utilizando
diferentes níveis de complexidade computacional.
Supondo que uma operação leva 1ms para ser
executado, e dado Tk(n) sendo a complexidade,
ou seja, o número de operações que o algoritmo
efetua para N entradas.
 Quais serão os tempos de execução de cada um
destes algoritmos?

Exemplo: Tempo de execução
N
A1
T1(n) = n
A2
T2(n) = n log n
A3
T3(n)=n2
A4
T4(n)= n3
A5
T(n)=2n
1
0.001s
0.016
0.064s
0.256s
4s
16
0.016s
0.064s
0.256s
4s
1m4s
32
0.032s
0.16s
1.0s
33s
46 dias
512
0.512s
9.0s
4m22s
1dia13h
10137 séculos
Tempo de execução em função do tamanho da entrada
Exemplo
Entrada : número N
 Saída
: número r representando a soma
dos N primeiros inteiros.

Exemplo: Fibonacci

A série tem a seguinte forma:

A função F(N) é definida por:
Implementação recursiva (exponencial):
Exemplo: Fibonacci
1. O algoritmo é correto?
2. Quanto tempo ele leva em função da entrada N?
3. O problema pode ser resolvido de uma maneira
melhor?
(1) sim! Ele é a implementação direta da
definição
 (2) T(n) – número de passos
computacionais

◦ Para n ≤ 2
◦ Para n > 2

Note que
Exemplo: Fibonacci

Quão demorada é a execução do algoritmo?
◦
◦
◦
◦

Fn ≈ 20,694n
F200 –> T(200) ≥ F200 ≥2138 passos computacionais
SC –> 40.1012 passos computacionais / segundo
fib1(200) @ SC = 292 segundos
(3) Existe uma maneira de se calcular
números da série de Fibonacci de maneira
mais eficiente?
◦ Lab!
Exemplo: Fibonacci
Chamadas recursivas de fib1(n)
Pontos Chave
Algoritmos são maneiras factíveis para solução de
problemas numéricos, no entanto eles precisam ser
analisados de modo a garantir sua eficácia;
 Análise de Algoritmos é uma disciplina que define
uma maneira sistemática de avaliação de algoritimos;
 Complexidade no Tempo e no Espaço definem
formas de estimarmos quanto tempo um programa
demora para se executar em função de sua entrada
assim como quanto espaço em disco ele requer;
 Notação Assintótica ou notação BigO é uma forma
de indicar a tendência de crescimento do tempo de
execução de algoritmos.

Para o Lar
Última chance para entregar o exercício
de nivelamento é dia 08/09 (prova 1)!;
 Ler o capítulo 0 (prólogo) do livro
“Algorithms” (Dasgupta) para a prova;
 Procure na internet uma forma mais
eficiente de calcular números fatoriais;
 Procure na internet uma forma mais
eficiente de ordenação de números que a
vista na aula.

Bibliografia


S. Dasgupta, C. H. Papadimitriou, U.V.Vazirani.
Algorithms, Chap. 0;
R. Sedgewick, Addison-Wesley. Algorithms in C, Parts 14: Fundamentals, Data Structures, Sorting, Searching, 3rd
edition, 1997.